-
A new upper limit on the axion-photon coupling with an extended CAST run with a Xe-based Micromegas detector
Authors:
CAST Collaboration,
K. Altenmüller,
V. Anastassopoulos,
S. Arguedas-Cuendis,
S. Aune,
J. Baier,
K. Barth,
H. Bräuninger,
G. Cantatore,
F. Caspers,
J. F. Castel,
S. A. Çetin,
F. Christensen,
C. Cogollos,
T. Dafni,
M. Davenport,
T. A. Decker,
K. Desch,
D. Díez-Ibáñez,
B. Döbrich,
E. Ferrer-Ribas,
H. Fischer,
W. Funk,
J. Galán,
J. A. García
, et al. (40 additional authors not shown)
Abstract:
Hypothetical axions provide a compelling explanation for dark matter and could be emitted from the hot solar interior. The CERN Axion Solar Telescope (CAST) has been searching for solar axions via their back conversion to X-ray photons in a 9-T 10-m long magnet directed towards the Sun. We report on an extended run with the IAXO (International Axion Observatory) pathfinder detector, doubling the p…
▽ More
Hypothetical axions provide a compelling explanation for dark matter and could be emitted from the hot solar interior. The CERN Axion Solar Telescope (CAST) has been searching for solar axions via their back conversion to X-ray photons in a 9-T 10-m long magnet directed towards the Sun. We report on an extended run with the IAXO (International Axion Observatory) pathfinder detector, doubling the previous exposure time. The detector was operated with a xenon-based gas mixture for part of the new run, providing technical insights for future detector configurations in IAXO. No counts are detected in the 95\% signal-encircling region during the new run, while one is expected. The new data improve the axion-photon coupling limit to 5.7$\times 10^{-11}\,$GeV$^{-1}$ at 95\% C.L., the most restrictive experimental limit to date.
△ Less
Submitted 24 June, 2024;
originally announced June 2024.
-
Euclid. IV. The NISP Calibration Unit
Authors:
Euclid Collaboration,
F. Hormuth,
K. Jahnke,
M. Schirmer,
C. G. -Y. Lee,
T. Scott,
R. Barbier,
S. Ferriol,
W. Gillard,
F. Grupp,
R. Holmes,
W. Holmes,
B. Kubik,
J. Macias-Perez,
M. Laurent,
J. Marpaud,
M. Marton,
E. Medinaceli,
G. Morgante,
R. Toledo-Moreo,
M. Trifoglio,
Hans-Walter Rix,
A. Secroun,
M. Seiffert,
P. Stassi
, et al. (310 additional authors not shown)
Abstract:
The near-infrared calibration unit (NI-CU) on board Euclid's Near-Infrared Spectrometer and Photometer (NISP) is the first astronomical calibration lamp based on light-emitting diodes (LEDs) to be operated in space. Euclid is a mission in ESA's Cosmic Vision 2015-2025 framework, to explore the dark universe and provide a next-level characterisation of the nature of gravitation, dark matter, and da…
▽ More
The near-infrared calibration unit (NI-CU) on board Euclid's Near-Infrared Spectrometer and Photometer (NISP) is the first astronomical calibration lamp based on light-emitting diodes (LEDs) to be operated in space. Euclid is a mission in ESA's Cosmic Vision 2015-2025 framework, to explore the dark universe and provide a next-level characterisation of the nature of gravitation, dark matter, and dark energy. Calibrating photometric and spectrometric measurements of galaxies to better than 1.5% accuracy in a survey homogeneously mapping ~14000 deg^2 of extragalactic sky requires a very detailed characterisation of near-infrared (NIR) detector properties, as well their constant monitoring in flight. To cover two of the main contributions - relative pixel-to-pixel sensitivity and non-linearity characteristics - as well as support other calibration activities, NI-CU was designed to provide spatially approximately homogeneous (<12% variations) and temporally stable illumination (0.1%-0.2% over 1200s) over the NISP detector plane, with minimal power consumption and energy dissipation. NI-CU is covers the spectral range ~[900,1900] nm - at cryo-operating temperature - at 5 fixed independent wavelengths to capture wavelength-dependent behaviour of the detectors, with fluence over a dynamic range of >=100 from ~15 ph s^-1 pixel^-1 to >1500 ph s^-1 pixel^-1. For this functionality, NI-CU is based on LEDs. We describe the rationale behind the decision and design process, describe the challenges in sourcing the right LEDs, as well as the qualification process and lessons learned. We also provide a description of the completed NI-CU, its capabilities and performance as well as its limits. NI-CU has been integrated into NISP and the Euclid satellite, and since Euclid's launch in July 2023 has started supporting survey operations.
△ Less
Submitted 10 July, 2024; v1 submitted 22 May, 2024;
originally announced May 2024.
-
The daily modulations and broadband strategy in axion searches. An application with CAST-CAPP detector
Authors:
C. M. Adair,
K. Altenmüller,
V. Anastassopoulos,
S. Arguedas Cuendis,
J. Baier,
K. Barth,
A. Belov,
D. Bozicevic,
H. Bräuninger,
G. Cantatore,
F. Caspers,
J. F. Castel,
S. A. Çetin,
W. Chung,
H. Choi,
J. Choi,
T. Dafni,
M. Davenport,
A. Dermenev,
K. Desch,
B. Döbrich,
H. Fischer,
W. Funk,
J. Galan,
A. Gardikiotis
, et al. (38 additional authors not shown)
Abstract:
It has been previously advocated that the presence of the daily and annual modulations of the axion flux on the Earth's surface may dramatically change the strategy of the axion searches. The arguments were based on the so-called Axion Quark Nugget (AQN) dark matter model which was originally put forward to explain the similarity of the dark and visible cosmological matter densities…
▽ More
It has been previously advocated that the presence of the daily and annual modulations of the axion flux on the Earth's surface may dramatically change the strategy of the axion searches. The arguments were based on the so-called Axion Quark Nugget (AQN) dark matter model which was originally put forward to explain the similarity of the dark and visible cosmological matter densities $Ω_{\rm dark}\sim Ω_{\rm visible}$. In this framework, the population of galactic axions with mass $ 10^{-6} {\rm eV}\lesssim m_a\lesssim 10^{-3}{\rm eV}$ and velocity $\langle v_a\rangle\sim 10^{-3} c$ will be accompanied by axions with typical velocities $\langle v_a\rangle\sim 0.6 c$ emitted by AQNs. Furthermore, in this framework, it has also been argued that the AQN-induced axion daily modulation (in contrast with the conventional WIMP paradigm) could be as large as $(10-20)\%$, which represents the main motivation for the present investigation. We argue that the daily modulations along with the broadband detection strategy can be very useful tools for the discovery of such relativistic axions. The data from the CAST-CAPP detector have been used following such arguments. Unfortunately, due to the dependence of the amplifier chain on temperature-dependent gain drifts and other factors, we could not conclusively show the presence or absence of a dark sector-originated daily modulation. However, this proof of principle analysis procedure can serve as a reference for future studies.
△ Less
Submitted 9 May, 2024;
originally announced May 2024.
-
Directed Evolution of Microorganisms for Engineered Living Materials
Authors:
Julie M. Laurent,
Ankit Jain,
Anton Kan,
Mathias Steinacher,
Nadia Enrriquez Casimiro,
Stavros Stavrakis,
Andrew J. deMello,
André R. Studart
Abstract:
Microorganisms can create engineered materials with exquisite structures and living functionalities. Although synthetic biology tools to genetically manipulate microorganisms continue to expand, the bottom-up rational design of engineered living materials still relies on prior knowledge of genotype-phenotype links for the function of interest. Here, we utilize a high-throughput directed evolution…
▽ More
Microorganisms can create engineered materials with exquisite structures and living functionalities. Although synthetic biology tools to genetically manipulate microorganisms continue to expand, the bottom-up rational design of engineered living materials still relies on prior knowledge of genotype-phenotype links for the function of interest. Here, we utilize a high-throughput directed evolution platform to enhance the fitness of whole microorganisms under selection pressure and identify novel genetic pathways to program the functionalities of engineered living materials. Using Komagataeibacter sucrofermentans as a model cellulose-producing microorganism, we show that our droplet-based microfluidic platform enables the directed evolution of these bacteria towards a small number of cellulose overproducers from an initial pool of 40'000 random mutants. Sequencing of the evolved strains reveals an unexpected link between the cellulose-forming ability of the bacteria and a gene encoding a protease complex responsible for protein turnover in the cell. The ability to enhance the fitness of microorganisms towards specific phenotypes and to discover new genotype-phenotype links makes this high-throughput directed evolution platform a promising tool for the development of the next generation of engineered living materials.
△ Less
Submitted 22 November, 2023;
originally announced November 2023.
-
Polymorphic Type Inference for Dynamic Languages
Authors:
Giuseppe Castagna,
Mickaël Laurent,
Kim Nguyen
Abstract:
We present a type system that combines, in a controlled way, first-order polymorphism with intersectiontypes, union types, and subtyping, and prove its safety. We then define a type reconstruction algorithm that issound and terminating. This yields a system in which unannotated functions are given polymorphic types(thanks to Hindley-Milner) that can express the overloaded behavior of the functions…
▽ More
We present a type system that combines, in a controlled way, first-order polymorphism with intersectiontypes, union types, and subtyping, and prove its safety. We then define a type reconstruction algorithm that issound and terminating. This yields a system in which unannotated functions are given polymorphic types(thanks to Hindley-Milner) that can express the overloaded behavior of the functions they type (thanks tothe intersection introduction rule) and that are deduced by applying advanced techniques of type narrowing(thanks to the union elimination rule). This makes the system a prime candidate to type dynamic languages.
△ Less
Submitted 17 November, 2023;
originally announced November 2023.
-
Comparative Analysis of Technical and Legal Frameworks of Various National Digial Identity Solutions
Authors:
Montassar Naghmouchi,
Maryline Laurent,
Claire Levallois-Barth,
Nesrine Kaaniche
Abstract:
National digital identity systems have become a key requirement for easy access to online public services, specially during Covid-19. While many countries have adopted a national digital identity system, many are still in the process of establishing one. Through a comparative analysis of the technological and legal dimensions of a few selected national digital identity solutions currently being us…
▽ More
National digital identity systems have become a key requirement for easy access to online public services, specially during Covid-19. While many countries have adopted a national digital identity system, many are still in the process of establishing one. Through a comparative analysis of the technological and legal dimensions of a few selected national digital identity solutions currently being used in different countries, we highlight the diversity of technologies and architectures and the key role of the legal framework of a given digital identity solution. We also present several key issues related to the implementation of these solutions, how to ensure the State sovereignty over them, and how to strike the right balance between private sector and public sector needs. This position paper aims to help policy makers, software developers and concerned users understand the challenges of designing, implementing and using a national digital identity management system and establishing a legal framework for digital identity management, including personal data protection measures. The authors of this paper have a favorable position for self-sovereign identity management systems that are based on Blockchain technology, and we believe they are the most suitable for national digital identity systems.
△ Less
Submitted 2 October, 2023;
originally announced October 2023.
-
Integrating Usage Control into Distributed Ledger Technology for Internet of Things Privacy
Authors:
Nathanaël Denis,
Maryline Laurent,
Sophie Chabridon
Abstract:
The Internet of Things brings new ways to collect privacy-sensitive data from billions of devices. Well-tailored distributed ledger technologies (DLTs) can provide high transaction processing capacities to IoT devices in a decentralized fashion. However, privacy aspects are often neglected or unsatisfying, with a focus mainly on performance and security. In this paper, we introduce decentralized u…
▽ More
The Internet of Things brings new ways to collect privacy-sensitive data from billions of devices. Well-tailored distributed ledger technologies (DLTs) can provide high transaction processing capacities to IoT devices in a decentralized fashion. However, privacy aspects are often neglected or unsatisfying, with a focus mainly on performance and security. In this paper, we introduce decentralized usage control mechanisms to empower IoT devices to control the data they generate. Usage control defines obligations, i.e., actions to be fulfilled to be granted access, and conditions on the system in addition to data dissemination control. The originality of this paper is to consider the usage control system as a component of distributed ledger networks, instead of an external tool. With this integration, both technologies work in synergy, benefiting their privacy, security and performance. We evaluated the performance improvements of integration using the IOTA technology, particularly suitable due to the participation of small devices in the consensus. The results of the tests on a private network show an approximate 90% decrease of the time needed for the UCS to push a transaction and make its access decision in the integrated setting, regardless of the number of nodes in the network.
△ Less
Submitted 9 June, 2023;
originally announced June 2023.
-
Maximum Likelihood Filtering for Particle Tracking in Turbulent Flows
Authors:
Griffin M. Kearney,
Kasey M. Laurent,
Reece V. Kearney
Abstract:
Lagrangian Particle Tracking (LPT) enables practitioners to study various concepts in turbulence by measuring particle positions in flows of interest. This data is subject to measurement errors, and filtering techniques are applied to mitigate these errors and improve the accuracy of analyses utilizing the data. We develop a new type of position filter through use of maximum likelihood estimation…
▽ More
Lagrangian Particle Tracking (LPT) enables practitioners to study various concepts in turbulence by measuring particle positions in flows of interest. This data is subject to measurement errors, and filtering techniques are applied to mitigate these errors and improve the accuracy of analyses utilizing the data. We develop a new type of position filter through use of maximum likelihood estimation by considering both measurement errors and stochastic process physics. The maximum likelihood estimation scheme we develop is general and can accommodate many different stochastic process models, enabling it to be applied to many different turbulent flows. In this work, we propose a process model similar to existing, complimentary work in the development of B-splines. We compare our filtering scheme to existing schemes and find that our filter out performs the scheme proposed by Mordant et al. (2004) considerably, and produces similar performance to spline filters, proposed by Gesemann (2018). In comparing to the latter, we note that the maximum likelihood treatment provides a general framework which is capable of producing different filters based on the physics of interest, whereas the spline filters are built on less specific filtering theory and are therefore more difficult to adapt across diverse use cases in fluids. We quantify the performance of each of the filtering methods using error metrics which consider both noise reduction as well as signal degradation, and together these are used to define a concept of filter efficiency. The maximum likelihood filter developed in this work is shown to be the most efficient among all the methods examined when applied to simulated isotropic turbulence data from the Johns Hopkins Database.
△ Less
Submitted 23 May, 2023;
originally announced May 2023.
-
Semidefinite approximations for bicliques and biindependent pairs
Authors:
Monique Laurent,
Sven Polak,
Luis Felipe Vargas
Abstract:
We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $α(G)$, well-known to be polynomial-time computa…
▽ More
We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $α(G)$, well-known to be polynomial-time computable. When maximizing the product $|A|\cdot |B|$ one finds the parameter $g(G)$, shown to be NP-hard by Peeters (2003), and when maximizing the ratio $|A|\cdot |B|/|A\cup B|$ one finds $h(G)$, introduced by Vallentin (2020) for bounding product-free sets in finite groups. We show that $h(G)$ is an NP-hard parameter and, as a crucial ingredient, that it is NP-complete to decide whether a bipartite graph $G$ has a balanced maximum independent set. These hardness results motivate introducing semidefinite programming bounds for $g(G)$, $h(G)$, and $α_{\text{bal}}(G)$ (the maximum cardinality of a balanced independent set). We show that these bounds can be seen as natural variations of the Lovász $\vartheta$-number, a well-known semidefinite bound on $α(G)$. In addition we formulate closed-form eigenvalue bounds and we show relationships among them as well as with earlier spectral parameters by Hoffman, Haemers (2001) and Vallentin (2020).
△ Less
Submitted 9 January, 2024; v1 submitted 17 February, 2023;
originally announced February 2023.
-
Copositive matrices, sums of squares and the stability number of a graph
Authors:
Luis Felipe Vargas,
Monique Laurent
Abstract:
This chapter investigates the cone of copositive matrices, with a focus on the design and analysis of conic inner approximations for it. These approximations are based on various sufficient conditions for matrix copositivity, relying on positivity certificates in terms of sums of squares of polynomials. Their application to the discrete optimization problem asking for a maximum stable set in a gra…
▽ More
This chapter investigates the cone of copositive matrices, with a focus on the design and analysis of conic inner approximations for it. These approximations are based on various sufficient conditions for matrix copositivity, relying on positivity certificates in terms of sums of squares of polynomials. Their application to the discrete optimization problem asking for a maximum stable set in a graph is also discussed. A central theme in this chapter is understanding when the conic approximations suffice for describing the full copositive cone, and when the corresponding bounds for the stable set problem admit finite convergence.
△ Less
Submitted 20 March, 2023; v1 submitted 9 February, 2023;
originally announced February 2023.
-
Rotation number of 2-interval piecewise affine maps
Authors:
José Pedro Gaivao,
Michel Laurent,
Arnaldo Nogueira
Abstract:
We study maps of the unit interval whose graph is made up of two increasing segments and which are injective in an extended sense. Such maps $f_{\p}$ are parametrized by a quintuple $\p$ of real numbers satisfying inequations. Viewing $f_{\p}$ as a circle map, we show that it has a rotation number $ρ(f_{\p})$ and we compute $ρ(f_{\p})$ as a function of $\p$ in terms of Hecke-Mahler series. As a co…
▽ More
We study maps of the unit interval whose graph is made up of two increasing segments and which are injective in an extended sense. Such maps $f_{\p}$ are parametrized by a quintuple $\p$ of real numbers satisfying inequations. Viewing $f_{\p}$ as a circle map, we show that it has a rotation number $ρ(f_{\p})$ and we compute $ρ(f_{\p})$ as a function of $\p$ in terms of Hecke-Mahler series. As a corollary, we prove that $ρ(f_{\p})$ is a rational number when the components of $\p$ are algebraic numbers.
△ Less
Submitted 21 December, 2022;
originally announced December 2022.
-
SPOT: Secure and Privacy-preserving prOximiTy protocol for e-healthcare systems
Authors:
Souha Masmoudi,
Nesrine Kaaniche,
Maryline Laurent
Abstract:
This paper introduces SPOT, a Secure and Privacy-preserving prOximity based protocol for e-healthcare systems. It relies on a distributed proxy-based approach to preserve users' privacy and a semi-trusted computing server to ensure data consistency and integrity. The proposed protocol ensures a balance between security, privacy and scalability. As far as we know, in terms of security, SPOT is the…
▽ More
This paper introduces SPOT, a Secure and Privacy-preserving prOximity based protocol for e-healthcare systems. It relies on a distributed proxy-based approach to preserve users' privacy and a semi-trusted computing server to ensure data consistency and integrity. The proposed protocol ensures a balance between security, privacy and scalability. As far as we know, in terms of security, SPOT is the first one to prevent malicious users from colluding and generating false positives. In terms of privacy, SPOT supports both anonymity of users being in proximity of infected people and unlinkability of contact information issued by the same user. A concrete construction based on structure-preserving signatures and NIWI proofs is proposed and a detailed security and privacy analysis proves that SPOT is secure under standard assumptions. In terms of scalability, SPOT's procedures and algorithms are implemented to show its efficiency and practical usability with acceptable computation and communication overhead.
△ Less
Submitted 1 December, 2022;
originally announced December 2022.
-
Search for Dark Matter Axions with CAST-CAPP
Authors:
C. M. Adair,
K. Altenmüller,
V. Anastassopoulos,
S. Arguedas Cuendis,
J. Baier,
K. Barth,
A. Belov,
D. Bozicevic,
H. Bräuninger,
G. Cantatore,
F. Caspers,
J. F. Castel,
S. A. Çetin,
W. Chung,
H. Choi,
J. Choi,
T. Dafni,
M. Davenport,
A. Dermenev,
K. Desch,
B. Döbrich,
H. Fischer,
W. Funk,
J. Galan,
A. Gardikiotis
, et al. (39 additional authors not shown)
Abstract:
The CAST-CAPP axion haloscope, operating at CERN inside the CAST dipole magnet, has searched for axions in the 19.74 $μ$eV to 22.47 $μ$eV mass range. The detection concept follows the Sikivie haloscope principle, where Dark Matter axions convert into photons within a resonator immersed in a magnetic field. The CAST-CAPP resonator is an array of four individual rectangular cavities inserted in a st…
▽ More
The CAST-CAPP axion haloscope, operating at CERN inside the CAST dipole magnet, has searched for axions in the 19.74 $μ$eV to 22.47 $μ$eV mass range. The detection concept follows the Sikivie haloscope principle, where Dark Matter axions convert into photons within a resonator immersed in a magnetic field. The CAST-CAPP resonator is an array of four individual rectangular cavities inserted in a strong dipole magnet, phase-matched to maximize the detection sensitivity. Here we report on the data acquired for 4124 h from 2019 to 2021. Each cavity is equipped with a fast frequency tuning mechanism of 10 MHz/min between 4.774 GHz and 5.434 GHz. In the present work, we exclude axion-photon couplings for virialized galactic axions down to $g_{aγγ} = 8 \times {10^{-14}}$ $GeV^{-1}$ at the 90% confidence level. The here implemented phase-matching technique also allows for future large-scale upgrades.
△ Less
Submitted 5 November, 2022;
originally announced November 2022.
-
Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
Authors:
Milan Korda,
Monique Laurent,
Victor Magron,
Andries Steenkamp
Abstract:
We explore a new type of sparsity for the generalized moment problem (GMP) that we call ideal-sparsity. This sparsity exploits the presence of equality constraints requiring the measure to be supported on the variety of an ideal generated by bilinear monomials modeled by an associated graph. We show that this enables an equivalent sparse reformulation of the GMP, where the single (high dimensional…
▽ More
We explore a new type of sparsity for the generalized moment problem (GMP) that we call ideal-sparsity. This sparsity exploits the presence of equality constraints requiring the measure to be supported on the variety of an ideal generated by bilinear monomials modeled by an associated graph. We show that this enables an equivalent sparse reformulation of the GMP, where the single (high dimensional) measure variable is replaced by several (lower-dimensional) measure variables supported on the maximal cliques of the graph. We explore the resulting hierarchies of moment-based relaxations for the original dense formulation of GMP and this new, equivalent ideal-sparse reformulation, when applied to the problem of bounding nonnegative- and completely positive matrix factorization ranks. We show that the ideal-sparse hierarchies provide bounds that are at least as good (and often tighter) as those obtained from the dense hierarchy. This is in sharp contrast to the situation when exploiting correlative sparsity, as is most common in the literature, where the resulting bounds are weaker than the dense bounds. Moreover, while correlative sparsity requires the underlying graph to be chordal, no such assumption is needed for ideal-sparsity. Numerical results show that the ideal-sparse bounds are often tighter and much faster to compute than their dense analogs.
△ Less
Submitted 9 July, 2023; v1 submitted 20 September, 2022;
originally announced September 2022.
-
On the Exactness of Sum-of-Squares Approximations for the Cone of $5\times 5$ Copositive Matrices
Authors:
Monique Laurent,
Luis Felipe Vargas
Abstract:
We investigate the hierarchy of conic inner approximations $\mathcal{K}^{(r)}_n$ ($r\in \mathbb{N}$) for the copositive cone $\text{COP}_n$, introduced by Parrilo (Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, PhD Thesis, California Institute of Technology, 2001). It is known that $\text{COP}_4=\mathcal{K}^{(0)}_4$ and that, while the union of…
▽ More
We investigate the hierarchy of conic inner approximations $\mathcal{K}^{(r)}_n$ ($r\in \mathbb{N}$) for the copositive cone $\text{COP}_n$, introduced by Parrilo (Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, PhD Thesis, California Institute of Technology, 2001). It is known that $\text{COP}_4=\mathcal{K}^{(0)}_4$ and that, while the union of the cones $\mathcal{K}^{(r)}_n$ covers the interior of $\text{COP}_n$, it does not cover the full cone $\text{COP}_n$ if $n\geq 6$. Here we investigate the remaining case $n=5$, where all extreme rays have been fully characterized by Hildebrand (The extreme rays of the 5 $\times$ 5 copositive cone. Linear Algebra and its Applications, 437(7):1538--1547, 2012). We show that the Horn matrix $H$ and its positive diagonal scalings play an exceptional role among the extreme rays of $\text{COP}_5$. We show that equality $\text{COP}_5=\bigcup_{r\geq 0} \mathcal{K}^{(r)}_5$ holds if and only if any positive diagonal scaling of $H$ belongs to $\mathcal{K}^{(r)}_5$ for some $r\in \mathbb{N}$. As a main ingredient for the proof, we introduce new Lasserre-type conic inner approximations for $\text{COP}_n$, based on sums of squares of polynomials. We show their links to the cones $\mathcal{K}^{(r)}_n$, and we use an optimization approach that permits to exploit finite convergence results on Lasserre hierarchy to show membership in the new cones.
△ Less
Submitted 11 May, 2022;
originally announced May 2022.
-
Enabling Fast and Flexible Distributed Deep Learning with Programmable Switches
Authors:
Heng Pan,
Penglai Cui,
Zhenyu li,
Ru Jia,
Penghao Zhang,
Leilei Zhang,
Ye Yang,
Jiahao Wu,
Jianbo Dong,
Zheng Cao,
Qiang Li,
Hongqiang Harry Liu,
Mathy Laurent,
Gaogang Xie
Abstract:
Deep learning has been used in a wide range of areas and made a huge breakthrough. With the ever-increasing model size and train-ing data volume, distributed deep learning emerges which utilizes a cluster to train a model in parallel. Unfortunately, the performance is often far from linear speedup due to the communication overhead between cluster nodes. To address this challenge, this paper design…
▽ More
Deep learning has been used in a wide range of areas and made a huge breakthrough. With the ever-increasing model size and train-ing data volume, distributed deep learning emerges which utilizes a cluster to train a model in parallel. Unfortunately, the performance is often far from linear speedup due to the communication overhead between cluster nodes. To address this challenge, this paper designs and implements Libra, a network aggregator, that utilizes in-network computation to optimize the communication for distributed DL training in two aspects: 1) reduce active connections and 2) aggregate exchanged network packets. We implemented our Libra on Intel Tofino switches, customized a lightweight host stack and integrated it into an open-source training framework PS-lite. The experimental result shows that our Libra can achieve 1.5~4 times speedup.
△ Less
Submitted 10 August, 2022; v1 submitted 10 May, 2022;
originally announced May 2022.
-
Transcendence and continued fraction expansion of values of Hecke-Mahler series
Authors:
Yann Bugeaud,
Michel Laurent
Abstract:
Let $θ$ and $ρ$ be real numbers with $0 \le θ, ρ< 1$ and $θ$ irrational. We show that the Hecke-Mahler series $$ F_{θ, ρ} (z_1, z_2) = \sum_{k_1 \ge 1} \, \sum_{k_2 = 1}^{\lfloor k_1 θ+ ρ\rfloor} \, z_1^{k_1} z_2^{k_2}, $$ where $\lfloor \cdot \rfloor$ denotes the integer part function, takes transcendental values at any algebraic point $(β, α)$ with $0 < |β|, |βα^θ| < 1$. This extends earlier res…
▽ More
Let $θ$ and $ρ$ be real numbers with $0 \le θ, ρ< 1$ and $θ$ irrational. We show that the Hecke-Mahler series $$ F_{θ, ρ} (z_1, z_2) = \sum_{k_1 \ge 1} \, \sum_{k_2 = 1}^{\lfloor k_1 θ+ ρ\rfloor} \, z_1^{k_1} z_2^{k_2}, $$ where $\lfloor \cdot \rfloor$ denotes the integer part function, takes transcendental values at any algebraic point $(β, α)$ with $0 < |β|, |βα^θ| < 1$. This extends earlier results of Mahler (1929) and Loxton and van der Poorten (1977), who settled the case $ρ=0$. Furthermore, for positive integers $b$ and $a$, with $b \ge 2$ and $a$ congruent to $1$ modulo $b-1$, we give the continued fraction expansion of the number
$$
{(b-1)^2\over b} F_{θ, ρ} \left({1\over b}, {1\over a}\right)+{\lfloor θ+ρ\rfloor(b-1)\over b^2a},
$$
from which we derive a formula giving the irrationality exponent of $F_{θ, ρ} (1/b, 1/a)$.
△ Less
Submitted 24 March, 2022;
originally announced March 2022.
-
An automatized Identity and Access Management system for IoT combining Self-Sovereign Identity and smart contracts
Authors:
Montassar Naghmouchi,
Hella Kaffel,
Maryline Laurent
Abstract:
Nowadays, open standards for self-sovereign identity and access management enable portable solutions that are following the requirements of IoT systems. This paper proposes a blockchain-based identity and access management system for IoT -- specifically smart vehicles -- as an example of use-case, showing two interoperable blockchains, Ethereum and Hyperledger Indy, and a self-sovereign identity m…
▽ More
Nowadays, open standards for self-sovereign identity and access management enable portable solutions that are following the requirements of IoT systems. This paper proposes a blockchain-based identity and access management system for IoT -- specifically smart vehicles -- as an example of use-case, showing two interoperable blockchains, Ethereum and Hyperledger Indy, and a self-sovereign identity model.
△ Less
Submitted 1 January, 2022;
originally announced January 2022.
-
Bounding the separable rank via polynomial optimization
Authors:
Sander Gribling,
Monique Laurent,
Andries Steenkamp
Abstract:
We investigate questions related to the set $\mathcal{SEP}_d$ consisting of the linear maps $ρ$ acting on $\mathbb{C}^d\otimes \mathbb{C}^d$ that can be written as a convex combination of rank one matrices of the form $xx^*\otimes yy^*$. Such maps are known in quantum information theory as the separable bipartite states, while nonseparable states are called entangled. In particular we introduce bo…
▽ More
We investigate questions related to the set $\mathcal{SEP}_d$ consisting of the linear maps $ρ$ acting on $\mathbb{C}^d\otimes \mathbb{C}^d$ that can be written as a convex combination of rank one matrices of the form $xx^*\otimes yy^*$. Such maps are known in quantum information theory as the separable bipartite states, while nonseparable states are called entangled. In particular we introduce bounds for the separable rank $\mathrm{rank_{sep}}(ρ)$, defined as the smallest number of rank one states $xx^*\otimes yy^*$ entering the decomposition of a separable state $ρ$. Our approach relies on the moment method and yields a hierarchy of semidefinite-based lower bounds, that converges to a parameter $τ_{\mathrm{sep}}(ρ)$, a natural convexification of the combinatorial parameter $\mathrm{rank_{sep}}(ρ)$. A distinguishing feature is exploiting the positivity constraint $ρ-xx^*\otimes yy^* \succeq 0$ to impose positivity of a polynomial matrix localizing map, the dual notion of the notion of sum-of-squares polynomial matrices. Our approach extends naturally to the multipartite setting and to the real separable rank, and it permits strengthening some known bounds for the completely positive rank. In addition, we indicate how the moment approach also applies to define hierarchies of semidefinite relaxations for the set $\mathcal{SEP}_d$ and permits to give new proofs, using only tools from moment theory, for convergence results on the DPS hierarchy from (A.C. Doherty, P.A. Parrilo and F.M. Spedalieri. Distinguishing separable and entangled states. Phys. Rev. Lett. 88(18):187904, 2002).
△ Less
Submitted 29 September, 2021;
originally announced September 2021.
-
Personal information self-management: A survey of technologies supporting administrative services
Authors:
Paul Marillonnet,
Maryline Laurent,
Mikaël Ates
Abstract:
This paper presents a survey of technologies for personal data self-management interfacing with administrative and territorial public service providers. It classifies a selection of scientific technologies into four categories of solutions: Personal Data Store (PDS), Identity Manager (IdM), Anonymous Certificate System and Access Control Delegation Architecture. Each category, along with its techn…
▽ More
This paper presents a survey of technologies for personal data self-management interfacing with administrative and territorial public service providers. It classifies a selection of scientific technologies into four categories of solutions: Personal Data Store (PDS), Identity Manager (IdM), Anonymous Certificate System and Access Control Delegation Architecture. Each category, along with its technological approach, is analyzed thanks to eighteen identified functional criteria that encompass architectural and communication aspects, as well as user data lifecycle considerations. The originality of the survey is multifold. First, as far as we know, there is no such thorough survey covering such a panel of a dozen of existing solutions. Second, it is the first survey addressing Personally Identifiable Information (PII) management for both administrative and private service providers. Third, this paper achieves a functional comparison of solutions of very different technical natures. The outcome of this paper is the clear identification of functional gaps of each solution. As a result, this paper establishes the research directions to follow in order to fill these functional gaps.
△ Less
Submitted 27 September, 2021;
originally announced September 2021.
-
Exactness of Parrilo's conic approximations for copositive matrices and associated low order bounds for the stability number of a graph
Authors:
Monique Laurent,
Luis Felipe Vargas
Abstract:
De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $α(G)$ of a graph $G$ and conjectured exactness at order $α(G)-1$: $\vartheta^{(α(G)-1)}(G)=α(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of…
▽ More
De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $α(G)$ of a graph $G$ and conjectured exactness at order $α(G)-1$: $\vartheta^{(α(G)-1)}(G)=α(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of $\vartheta^{(r)}$ is the bad behaviour of the cones $\mathcal{K}_n^{(r)}$ under adding a zero row/column: when applied to a matrix not in $\mathcal{K}^{(0)}_n$ this gives a matrix not in any ${\mathcal{K}}^{(r)}_{n+1}$, thereby showing strict inclusion $\bigcup_{r\ge 0}{\mathcal{K}}^{(r)}_n\subset \text{COP}_n$ for $n\ge 6$. We investigate the graphs with $\vartheta^{(r)}(G)=α(G)$ for $r=0,1$: we algorithmically reduce testing exactness of $\vartheta^{(0)}$ to acritical graphs, we characterize critical graphs with $\vartheta^{(0)}$ exact, and we exhibit graphs for which exactness of $\vartheta^{(1)}$ is not preserved under adding an isolated node. This disproves a conjecture by Gvozdenović and Laurent (2007) which, if true, would have implied the above conjecture by de Klerk and Pasechnik.
△ Less
Submitted 27 September, 2021;
originally announced September 2021.
-
A Validated Privacy-Utility Preserving Recommendation System with Local Differential Privacy
Authors:
Seryne Rahali,
Maryline Laurent,
Souha Masmoudi,
Charles Roux,
Brice Mazeau
Abstract:
This paper proposes a new recommendation system preserving both privacy and utility. It relies on the local differential privacy (LDP) for the browsing user to transmit his noisy preference profile, as perturbed Bloom filters, to the service provider. The originality of the approach is multifold. First, as far as we know, the approach is the first one including at the user side two perturbation ro…
▽ More
This paper proposes a new recommendation system preserving both privacy and utility. It relies on the local differential privacy (LDP) for the browsing user to transmit his noisy preference profile, as perturbed Bloom filters, to the service provider. The originality of the approach is multifold. First, as far as we know, the approach is the first one including at the user side two perturbation rounds - PRR (Permanent Randomized Response) and IRR (Instantaneous Randomized Response) - over a complete user profile. Second, a full validation experimentation chain is set up, with a machine learning decoding algorithm based on neural network or XGBoost for decoding the perturbed Bloom filters and the clustering Kmeans tool for clustering users. Third, extensive experiments show that our method achieves good utility-privacy trade-off, i.e. a 90$\%$ clustering success rate, resp. 80.3$\%$ for a value of LDP $ε= 0.8$, resp. $ε= 2$. Fourth, an experimental and theoretical analysis gives concrete results on the resistance of our approach to the plausible deniability and resistance against averaging attacks.
△ Less
Submitted 23 September, 2021;
originally announced September 2021.
-
An effective version of Schmüdgen's Positivstellensatz for the hypercube
Authors:
Monique Laurent,
Lucas Slot
Abstract:
Let $S \subseteq \mathbb{R}^n$ be a compact semialgebraic set and let $f$ be a polynomial nonnegative on $S$. Schmüdgen's Positivstellensatz then states that for any $η> 0$, the nonnegativity of $f + η$ on $S$ can be certified by expressing $f + η$ as a conic combination of products of the polynomials that occur in the inequalities defining $S$, where the coefficients are (globally nonnegative) su…
▽ More
Let $S \subseteq \mathbb{R}^n$ be a compact semialgebraic set and let $f$ be a polynomial nonnegative on $S$. Schmüdgen's Positivstellensatz then states that for any $η> 0$, the nonnegativity of $f + η$ on $S$ can be certified by expressing $f + η$ as a conic combination of products of the polynomials that occur in the inequalities defining $S$, where the coefficients are (globally nonnegative) sum-of-squares polynomials. It does not, however, provide explicit bounds on the degree of the polynomials required for such an expression. We show that in the special case where $S = [-1, 1]^n$ is the hypercube, a Schmüdgen-type certificate of nonnegativity exists involving only polynomials of degree $O(1 / \sqrtη)$. This improves quadratically upon the previously best known estimate in $O(1/η)$. Our proof relies on an application of the polynomial kernel method, making use in particular of the Jackson kernel on the interval $[-1, 1]$.
△ Less
Submitted 2 February, 2023; v1 submitted 20 September, 2021;
originally announced September 2021.
-
Merit and Blame Assignment with Kind 2
Authors:
Daniel Larraz,
Mickaël Laurent,
Cesare Tinelli
Abstract:
We introduce two new major features of the open-source model checker Kind 2 which provide traceability information between specification and design elements such as assumptions, guarantees, or other behavioral constraints in synchronous reactive system models. This new version of Kind 2 can identify minimal sets of design elements, known as Minimal Inductive Validity Cores, which are sufficient to…
▽ More
We introduce two new major features of the open-source model checker Kind 2 which provide traceability information between specification and design elements such as assumptions, guarantees, or other behavioral constraints in synchronous reactive system models. This new version of Kind 2 can identify minimal sets of design elements, known as Minimal Inductive Validity Cores, which are sufficient to prove a given set of safety properties, and also determine the set of MUST elements, design elements that are necessary to prove the given properties. In addition, Kind 2 is able to find minimal sets of design constraints, known as Minimal Cut Sets, whose violation leads the system to an unsafe state. The computed information can be used for several purposes, including assessing the quality of a system specification, tracking the safety impact of model changes, and analyzing the tolerance and resilience of a system against faults or cyber-attacks. We describe these new capabilities in some detail and report on an initial experimental evaluation of some of them.
△ Less
Submitted 13 May, 2021;
originally announced May 2021.
-
First results of the CAST-RADES haloscope search for axions at 34.67 $μ$eV
Authors:
A. Álvarez Melcón,
S. Arguedas Cuendis,
J. Baier,
K. Barth,
H. Bräuniger,
S. Calatroni,
G. Cantatore,
F. Caspers,
J. F Castel,
S. A. Cetin,
C. Cogollos,
T. Dafni,
M. Davenport,
A. Dermenev,
K. Desch,
A. Díaz-Morcillo,
B. Döbrich,
H. Fischer,
W. Funk,
J. D Gallego,
J. M García Barceló,
A. Gardikiotis,
J. Garza,
B. Gimeno,
S. Gninenko
, et al. (34 additional authors not shown)
Abstract:
We present results of the Relic Axion Dark-Matter Exploratory Setup (RADES), a detector which is part of the CERN Axion Solar Telescope (CAST), searching for axion dark matter in the 34.67$μ$eV mass range. A radio frequency cavity consisting of 5 sub-cavities coupled by inductive irises took physics data inside the CAST dipole magnet for the first time using this filter-like haloscope geometry. An…
▽ More
We present results of the Relic Axion Dark-Matter Exploratory Setup (RADES), a detector which is part of the CERN Axion Solar Telescope (CAST), searching for axion dark matter in the 34.67$μ$eV mass range. A radio frequency cavity consisting of 5 sub-cavities coupled by inductive irises took physics data inside the CAST dipole magnet for the first time using this filter-like haloscope geometry. An exclusion limit with a 95% credibility level on the axion-photon coupling constant of g$_{aγ}\gtrsim 4\times10^{-13} \text{GeV}^{-1}$ over a mass range of 34.6738 $μ$eV < $m_a$ < 34.6771 $μ$eV is set. This constitutes a significant improvement over the current strongest limit set by CAST at this mass and is at the same time one of the most sensitive direct searches for an axion dark matter candidate above the mass of 25 $μ$eV. The results also demonstrate the feasibility of exploring a wider mass range around the value probed by CAST-RADES in this work using similar coherent resonant cavities.
△ Less
Submitted 27 October, 2021; v1 submitted 28 April, 2021;
originally announced April 2021.
-
Combinatorial structure of Sturmian words and continued fraction expansions of Sturmian numbers
Authors:
Yann Bugeaud,
Michel Laurent
Abstract:
Let $θ= [0; a_1, a_2, \dots]$ be the continued fraction expansion of an irrational real number $θ\in (0, 1)$. It is well-known that the characteristic Sturmian word of slope $θ$ is the limit of a sequence of finite words $(M_k)_{k \ge 0}$, with $M_k$ of length $q_k$ (the denominator of the $k$-th convergent to $θ$) being a suitable concatenation of $a_k$ copies of $M_{k-1}$ and one copy of…
▽ More
Let $θ= [0; a_1, a_2, \dots]$ be the continued fraction expansion of an irrational real number $θ\in (0, 1)$. It is well-known that the characteristic Sturmian word of slope $θ$ is the limit of a sequence of finite words $(M_k)_{k \ge 0}$, with $M_k$ of length $q_k$ (the denominator of the $k$-th convergent to $θ$) being a suitable concatenation of $a_k$ copies of $M_{k-1}$ and one copy of $M_{k-2}$. Our first result extends this to any Sturmian word. Let $b \ge 2$ be an integer. Our second result gives the continued fraction expansion of any real number $ξ$ whose $b$-ary expansion is a Sturmian word ${\bf s}$ over the alphabet $\{0, b-1\}$. This extends a classical result of Böhmer who considered only the case where ${\bf s}$ is characteristic. As a consequence, we obtain a formula for the irrationality exponent of $ξ$ in terms of the slope and the intercept of ${\bf s}$.
△ Less
Submitted 19 April, 2021;
originally announced April 2021.
-
Finite convergence of sum-of-squares hierarchies for the stability number of a graph
Authors:
Monique Laurent,
Luis Felipe Vargas
Abstract:
We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $α(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [{\em SIAM J. Optim.} 12 (2002), pp.875--892], who conjectured convergence to $α(G)$ in $r=α(G)-1$ steps. Even the weaker conjecture claiming finite convergence is still open. We establish lin…
▽ More
We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $α(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [{\em SIAM J. Optim.} 12 (2002), pp.875--892], who conjectured convergence to $α(G)$ in $r=α(G)-1$ steps. Even the weaker conjecture claiming finite convergence is still open. We establish links between this hierarchy and sum-of-squares hierarchies based on the Motzkin-Straus formulation of $α(G)$, which we use to show finite convergence when $G$ is acritical, i.e., when $α(G\setminus e)=α(G)$ for all edges $e$ of $G$. This relies, in particular, on understanding the structure of the minimizers of the Motzkin-Straus formulation and showing that their number is finite precisely when $G$ is acritical. Moreover we show that these results hold in the general setting of the weighted stable set problem for graphs equipped with positive node weights. In addition, as a byproduct we show that deciding whether a standard quadratic program has finitely many minimizers does not admit a polynomial-time algorithm unless P=NP.
△ Less
Submitted 22 January, 2024; v1 submitted 2 March, 2021;
originally announced March 2021.
-
Turbulence explains the accelerations of an eagle in natural flight
Authors:
Kasey M. Laurent,
Bob Fogg,
Tobias Ginsburg,
Casey Halverson,
Michael Lanzone,
Tricia A. Miller,
David W. Winkler,
Gregory P. Bewley
Abstract:
Turbulent winds and gusts fluctuate on a wide range of timescales from milliseconds to minutes and longer, a range that overlaps the timescales of avian flight behavior, yet the importance of turbulence to avian behavior is unclear. By combining wind speed data with the measured accelerations of a golden eagle (Aquila chrysaetos) flying in the wild, we show that the eagle's accelerations can be ex…
▽ More
Turbulent winds and gusts fluctuate on a wide range of timescales from milliseconds to minutes and longer, a range that overlaps the timescales of avian flight behavior, yet the importance of turbulence to avian behavior is unclear. By combining wind speed data with the measured accelerations of a golden eagle (Aquila chrysaetos) flying in the wild, we show that the eagle's accelerations can be explained by a linear interaction with turbulence for timescales between about 1/2 and 10 s. These timescales are comparable to those of typical eagle behaviors, corresponding to between about 1 and 25 wingbeats, and to those of turbulent gusts both larger than the eagle's wingspan and smaller than large-scale atmospheric phenomena such as convection cells. The eagle's accelerations exhibit power spectra and intermittent activity characteristic of turbulence, and increase in proportion to the turbulence intensity. Intermittency results in accelerations that are occasionally several times stronger than gravity, and much larger than the ones we experience while driving, for instance. These imprints of turbulence on the bird's movements need to be further explored to understand the energetics of birds and other volant lifeforms, to improve our own methods of flying through ceaselessly turbulent environments, and to engage airborne wildlife as distributed probes of the changing conditions in the atmosphere.
△ Less
Submitted 19 May, 2021; v1 submitted 19 February, 2021;
originally announced February 2021.
-
Sum-of-squares hierarchies for binary polynomial optimization
Authors:
Lucas Slot,
Monique Laurent
Abstract:
We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial $f$ over the boolean hypercube $\mathbb{B}^{n}=\{0,1\}^n$. This hierarchy provides for each integer $r \in \mathbb{N}$ a lower bound $f_{(r)}$ on the minimum $f_{\min}$ of $f$, given by the largest scalar $λ$ for which the polynomial $f - λ$ is a sum-of-squares on $\mathbb{B}^{n}$ with degree at m…
▽ More
We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial $f$ over the boolean hypercube $\mathbb{B}^{n}=\{0,1\}^n$. This hierarchy provides for each integer $r \in \mathbb{N}$ a lower bound $f_{(r)}$ on the minimum $f_{\min}$ of $f$, given by the largest scalar $λ$ for which the polynomial $f - λ$ is a sum-of-squares on $\mathbb{B}^{n}$ with degree at most $2r$. We analyze the quality of these bounds by estimating the worst-case error $f_{\min} - f_{(r)}$ in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed $t \in [0, 1/2]$, we can show that this worst-case error in the regime $r \approx t \cdot n$ is of the order $1/2 - \sqrt{t(1-t)}$ as $n$ tends to $\infty$. Our proof combines classical Fourier analysis on $\mathbb{B}^{n}$ with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds $f_{(r)}$ and another hierarchy of upper bounds $f^{(r)}$, for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the $q$-ary cube $(\mathbb{Z}/q\mathbb{Z})^{n}$.
△ Less
Submitted 19 January, 2022; v1 submitted 8 November, 2020;
originally announced November 2020.
-
Optimizing hypergraph-based polynomials modeling job-occupancy in queueing with redundancy scheduling
Authors:
Daniel Brosch,
Monique Laurent,
Andries Steenkamp
Abstract:
We investigate two classes of multivariate polynomials with variables indexed by the edges of a uniform hypergraph and coefficients depending on certain patterns of union of edges. These polynomials arise naturally to model job-occupancy in some queuing problems with redundancy scheduling policy. The question, posed by Cardinaels, Borst and van Leeuwaarden (arXiv:2005.14566, 2020), is to decide wh…
▽ More
We investigate two classes of multivariate polynomials with variables indexed by the edges of a uniform hypergraph and coefficients depending on certain patterns of union of edges. These polynomials arise naturally to model job-occupancy in some queuing problems with redundancy scheduling policy. The question, posed by Cardinaels, Borst and van Leeuwaarden (arXiv:2005.14566, 2020), is to decide whether their global minimum over the standard simplex is attained at the uniform probability distribution. By exploiting symmetry properties of these polynomials we can give a positive answer for the first class and partial results for the second one, where we in fact show a stronger convexity property of these polynomials over the simplex.
△ Less
Submitted 9 September, 2020;
originally announced September 2020.
-
Recommending Podcasts for Cold-Start Users Based on Music Listening and Taste
Authors:
Zahra Nazari,
Christophe Charbuillet,
Johan Pages,
Martin Laurent,
Denis Charrier,
Briana Vecchione,
Ben Carterette
Abstract:
Recommender systems are increasingly used to predict and serve content that aligns with user taste, yet the task of matching new users with relevant content remains a challenge. We consider podcasting to be an emerging medium with rapid growth in adoption, and discuss challenges that arise when applying traditional recommendation approaches to address the cold-start problem. Using music consumptio…
▽ More
Recommender systems are increasingly used to predict and serve content that aligns with user taste, yet the task of matching new users with relevant content remains a challenge. We consider podcasting to be an emerging medium with rapid growth in adoption, and discuss challenges that arise when applying traditional recommendation approaches to address the cold-start problem. Using music consumption behavior, we examine two main techniques in inferring Spotify users preferences over more than 200k podcasts. Our results show significant improvements in consumption of up to 50\% for both offline and online experiments. We provide extensive analysis on model performance and examine the degree to which music data as an input source introduces bias in recommendations.
△ Less
Submitted 26 July, 2020;
originally announced July 2020.
-
Securing Organization's Data: A Role-Based Authorized Keyword Search Scheme with Efficient Decryption
Authors:
Nazatul Haque Sultan,
Maryline Laurent,
Vijay Varadharajan
Abstract:
For better data availability and accessibility while ensuring data secrecy, organizations often tend to outsource their encrypted data to the cloud storage servers, thus bringing the challenge of keyword search over encrypted data. In this paper, we propose a novel authorized keyword search scheme using Role-Based Encryption (RBE) technique in a cloud environment. The contributions of this paper a…
▽ More
For better data availability and accessibility while ensuring data secrecy, organizations often tend to outsource their encrypted data to the cloud storage servers, thus bringing the challenge of keyword search over encrypted data. In this paper, we propose a novel authorized keyword search scheme using Role-Based Encryption (RBE) technique in a cloud environment. The contributions of this paper are multi-fold. First, it presents a keyword search scheme which enables only the authorized users, having proper assigned roles, to delegate keyword-based data search capabilities over encrypted data to the cloud providers without disclosing any sensitive information. Second, it supports a multi-organization cloud environment, where the users can be associated with more than one organization. Third, the proposed scheme provides efficient decryption, conjunctive keyword search and revocation mechanisms. Fourth, the proposed scheme outsources expensive cryptographic operations in decryption to the cloud in a secure manner. Fifth, we have provided a formal security analysis to prove that the proposed scheme is semantically secure against Chosen Plaintext and Chosen Keyword Attacks. Finally, our performance analysis shows that the proposed scheme is suitable for practical applications.
△ Less
Submitted 22 April, 2020;
originally announced April 2020.
-
Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
Authors:
Lucas Slot,
Monique Laurent
Abstract:
We consider a hierarchy of upper approximations for the minimization of a polynomial $f$ over a compact set $K \subseteq \mathbb{R}^n$ proposed recently by Lasserre (arXiv:1907.097784, 2019). This hierarchy relies on using the push-forward measure of the Lebesgue measure on $K$ by the polynomial $f$ and involves univariate sums of squares of polynomials with growing degrees $2r$. Hence it is weake…
▽ More
We consider a hierarchy of upper approximations for the minimization of a polynomial $f$ over a compact set $K \subseteq \mathbb{R}^n$ proposed recently by Lasserre (arXiv:1907.097784, 2019). This hierarchy relies on using the push-forward measure of the Lebesgue measure on $K$ by the polynomial $f$ and involves univariate sums of squares of polynomials with growing degrees $2r$. Hence it is weaker, but cheaper to compute, than an earlier hierarchy by Lasserre (SIAM Journal on Optimization 21(3), 864--885, 2011), which uses multivariate sums of squares. We show that this new hierarchy converges to the global minimum of $f$ at a rate in $O(\log^2 r / r^2)$ whenever $K$ satisfies a mild geometric condition, which holds, e.g., for convex bodies and for compact semialgebraic sets with dense interior. As an application this rate of convergence also applies to the stronger hierarchy based on multivariate sums of squares, which improves and extends earlier convergence results to a wider class of compact sets. Furthermore, we show that our analysis is near-optimal by proving a lower bound on the convergence rate in $Ω(1/r^2)$ for a class of polynomials on $K=[-1,1]$, obtained by exploiting a connection to orthogonal polynomials.
△ Less
Submitted 3 December, 2020; v1 submitted 30 January, 2020;
originally announced January 2020.
-
On the Diophantine nature of the elements of Cantor sets arising in the dynamics of contracted rotations
Authors:
Yann Bugeaud,
Dong Han Kim,
Michel Laurent,
Arnaldo Nogueira
Abstract:
We prove that these Cantor sets are made up of transcendental numbers, apart from their endpoints $0$ and $1$, under some arithmetical assumptions on the data. To that purpose, we establish a criterion of linear independence over the field of algebraic numbers for the three numbers $1$, a characteristic Sturmian number, and an arbitrary Sturmian number with the same slope.
We prove that these Cantor sets are made up of transcendental numbers, apart from their endpoints $0$ and $1$, under some arithmetical assumptions on the data. To that purpose, we establish a criterion of linear independence over the field of algebraic numbers for the three numbers $1$, a characteristic Sturmian number, and an arbitrary Sturmian number with the same slope.
△ Less
Submitted 2 January, 2020;
originally announced January 2020.
-
Dynamics of 2-interval piecewise affine maps and Hecke-Mahler series
Authors:
Michel Laurent,
Arnaldo Nogueira
Abstract:
Let $f : [0,1)\rightarrow [0,1)$ be a $2$-interval piecewise affine increasing map which is injective but not surjective. Such a map $f$ has a rotation number and can be parametrized by three real numbers. We make fully explicit the dynamics of $f$ thanks to two specific functions $δ$ and $φ$ depending on these parameters whose definitions involve Hecke-Mahler series. As an application, we show th…
▽ More
Let $f : [0,1)\rightarrow [0,1)$ be a $2$-interval piecewise affine increasing map which is injective but not surjective. Such a map $f$ has a rotation number and can be parametrized by three real numbers. We make fully explicit the dynamics of $f$ thanks to two specific functions $δ$ and $φ$ depending on these parameters whose definitions involve Hecke-Mahler series. As an application, we show that the rotation number of $f$ is rational, when the three parameters are algebraic numbers.
△ Less
Submitted 19 July, 2019;
originally announced July 2019.
-
Revisiting Occurrence Typing
Authors:
Giuseppe Castagna,
Victor Lanvin,
Mickaël Laurent,
Kim Nguyen
Abstract:
We revisit occurrence typing, a technique to refine the type of variables occurring in type-cases and, thus, capturesome programming patterns used in untyped languages. Although occurrence typing was tied from its inceptionto set-theoretic types-union types, in particular-it never fully exploited the capabilities of these types. Here weshow how, by using set-theoretic types, it is possible to deve…
▽ More
We revisit occurrence typing, a technique to refine the type of variables occurring in type-cases and, thus, capturesome programming patterns used in untyped languages. Although occurrence typing was tied from its inceptionto set-theoretic types-union types, in particular-it never fully exploited the capabilities of these types. Here weshow how, by using set-theoretic types, it is possible to develop a general typing framework that encompasses andgeneralizes several aspects of current occurrence typing proposals and that can be applied to tackle other problemssuch as the reconstruction of intersection types for unannotated or partially annotated functions and the optimizationof the compilation of gradually typed languages.
△ Less
Submitted 12 February, 2022; v1 submitted 12 July, 2019;
originally announced July 2019.
-
First Results on the Search for Chameleons with the KWISP Detector at CAST
Authors:
S. Arguedas Cuendis,
J. Baier,
K. Barth,
S. Baum,
A. Bayirli,
A. Belov,
H. Bräuninger,
G. Cantatore,
J. M. Carmona,
J. F. Castel,
S. A. Cetin,
T. Dafni,
M. Davenport,
A. Dermenev,
K. Desch,
B. Döbrich,
H. Fischer,
W. Funk,
J. A. García,
A. Gardikiotis,
J. G. Garza,
S. Gninenko,
M. D. Hasinoff,
D. H. H. Hoffmann,
F. J. Iguaz
, et al. (28 additional authors not shown)
Abstract:
We report on a first measurement with a sensitive opto-mechanical force sensor designed for the direct detection of coupling of real chameleons to matter. These dark energy candidates could be produced in the Sun and stream unimpeded to Earth. The KWISP detector installed on the CAST axion search experiment at CERN looks for tiny displacements of a thin membrane caused by the mechanical effect of…
▽ More
We report on a first measurement with a sensitive opto-mechanical force sensor designed for the direct detection of coupling of real chameleons to matter. These dark energy candidates could be produced in the Sun and stream unimpeded to Earth. The KWISP detector installed on the CAST axion search experiment at CERN looks for tiny displacements of a thin membrane caused by the mechanical effect of solar chameleons. The displacements are detected by a Michelson interferometer with a homodyne readout scheme. The sensor benefits from the focusing action of the ABRIXAS X-ray telescope installed at CAST, which increases the chameleon flux on the membrane. A mechanical chopper placed between the telescope output and the detector modulates the incoming chameleon stream. We present the results of the solar chameleon measurements taken at CAST in July 2017, setting an upper bound on the force acting on the membrane of $80$~pN at 95\% confidence level. The detector is sensitive for direct coupling to matter $10^4 \leqβ_m \leq 10^8$, where the coupling to photons is locally bound to $β_γ\leq 10^{11}$.
△ Less
Submitted 3 June, 2019;
originally announced June 2019.
-
Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
Authors:
Lucas Slot,
Monique Laurent
Abstract:
We consider the problem of computing the minimum value $f_{\min,K}$ of a polynomial $f$ over a compact set $K \subseteq \mathbb{R}^n$, which can be reformulated as finding a probability measure $ν$ on $K$ minimizing $\int_K f dν$. Lasserre showed that it suffices to consider such measures of the form $ν= qμ$, where $q$ is a sum-of-squares polynomial and $μ$ is a given Borel measure supported on…
▽ More
We consider the problem of computing the minimum value $f_{\min,K}$ of a polynomial $f$ over a compact set $K \subseteq \mathbb{R}^n$, which can be reformulated as finding a probability measure $ν$ on $K$ minimizing $\int_K f dν$. Lasserre showed that it suffices to consider such measures of the form $ν= qμ$, where $q$ is a sum-of-squares polynomial and $μ$ is a given Borel measure supported on $K$. By bounding the degree of $q$ by $2r$ one gets a converging hierarchy of upper bounds $f^{(r)}$ for $f_{\min,K}$. When $K$ is the hypercube $[-1, 1]^n$, equipped with the Chebyshev measure, the parameters $f^{(r)}$ are known to converge to $f_{\min,K}$ at a rate in $O(1/r^2)$. We extend this error estimate to a wider class of convex bodies, while also allowing for a broader class of reference measures, including the Lebesgue measure. Our analysis applies to simplices, balls and convex bodies that locally look like a ball. In addition, we show an error estimate in $O(\log r / r)$ when $K$ satisfies a minor geometrical condition, and in $O(\log^2 r / r^2)$ when $K$ is a convex body, equipped with the Lebesgue measure. This improves upon the currently best known error estimates in $O(1 / \sqrt{r})$ and $O(1/r)$ for these two respective cases.
△ Less
Submitted 30 January, 2020; v1 submitted 20 May, 2019;
originally announced May 2019.
-
Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
Authors:
Etienne de Klerk,
Monique Laurent
Abstract:
We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the prob…
▽ More
We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respect to the surface measure.
We show that the exact rate of convergence is Theta(1/r^2), and explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.
△ Less
Submitted 18 April, 2019;
originally announced April 2019.
-
Semidefinite programming formulations for the completely bounded norm of a tensor
Authors:
Sander Gribling,
Monique Laurent
Abstract:
We show that a certain tensor norm, the completely bounded norm, can be expressed by a semidefinite program. This tensor norm recently attracted attention in the field of quantum computing, where it was used by Arunachalam, Briët and Palazuelos for characterizing the quantum query complexity of Boolean functions. Combined with their results, we obtain a new characterization of the quantum query co…
▽ More
We show that a certain tensor norm, the completely bounded norm, can be expressed by a semidefinite program. This tensor norm recently attracted attention in the field of quantum computing, where it was used by Arunachalam, Briët and Palazuelos for characterizing the quantum query complexity of Boolean functions. Combined with their results, we obtain a new characterization of the quantum query complexity through semidefinite programming. Using the duality theory of semidefinite programming we obtain a new type of certificates for large query complexity. We show that our class of certificates encompasses the linear programming certificates corresponding to the approximate degree of a Boolean function.
△ Less
Submitted 15 January, 2019;
originally announced January 2019.
-
A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis
Authors:
Etienne de Klerk,
Monique Laurent
Abstract:
The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution app…
▽ More
The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution approach, due to J.B. Lasserre, is to approximate the convex cone of positive Borel measures by finite dimensional outer and inner conic approximations. We will review some results on these approximations, with a special focus on the convergence rate of the hierarchies of upper and lower bounds for the general problem of moments that are obtained from these inner and outer approximations.
△ Less
Submitted 13 November, 2018;
originally announced November 2018.
-
Improved Search for Solar Chameleons with a GridPix Detector at CAST
Authors:
V. Anastassopoulos,
S. Aune,
K. Barth,
A. Belov,
H. Bräuninger,
G. Cantatore,
J. M. Carmona,
J. F. Castel,
S. A. Cetin,
F. Christensen,
T. Dafni,
M. Davenport,
A. Dermenev,
K. Desch,
B. Döbrich,
C. Eleftheriadis,
G. Fanourakis,
E. Ferrer-Ribas,
H. Fischer,
W. Funk,
J. A. García,
A. Gardikiotis,
J. G. Garza,
E. N. Gazis,
T. Geralis
, et al. (44 additional authors not shown)
Abstract:
We report on a new search for solar chameleons with the CERN Axion Solar Telescope (CAST). A GridPix detector was used to search for soft X-ray photons in the energy range from 200 eV to 10 keV from converted solar chameleons. No signiffcant excess over the expected background has been observed in the data taken in 2014 and 2015. We set an improved limit on the chameleon photon coupling,…
▽ More
We report on a new search for solar chameleons with the CERN Axion Solar Telescope (CAST). A GridPix detector was used to search for soft X-ray photons in the energy range from 200 eV to 10 keV from converted solar chameleons. No signiffcant excess over the expected background has been observed in the data taken in 2014 and 2015. We set an improved limit on the chameleon photon coupling, $β_γ< 5.7\times10^{10}$ for $1<β_\mathrm{m}<10^6$ at 95% C.L. improving our previous results by a factor two and for the first time reaching sensitivity below the solar luminosity bound for tachocline magnetic fields up to $12.5\,\mathrm{T}$.
△ Less
Submitted 8 November, 2018; v1 submitted 31 July, 2018;
originally announced August 2018.
-
A data-supported history of bioinformatics tools
Authors:
Levin Clément,
Dynomant Emeric,
Gonzalez Bruno J,
Mouchard Laurent,
Landsman David,
Hovig Eivind,
Vlahovicek Kristian
Abstract:
Since the advent of next-generation sequencing in the early 2000s, the volume of bioinformatics software tools and databases has exploded and continues to grow rapidly. Documenting this evolution on a global and time-dependent scale is a challenging task, limited by the scarcity of comprehensive tool repositories. We collected data from over ~23,000 references classified in the OMICtools database,…
▽ More
Since the advent of next-generation sequencing in the early 2000s, the volume of bioinformatics software tools and databases has exploded and continues to grow rapidly. Documenting this evolution on a global and time-dependent scale is a challenging task, limited by the scarcity of comprehensive tool repositories. We collected data from over ~23,000 references classified in the OMICtools database, spanning the last 26 years of bioinformatics to present a data-supported snapshot of bioinformatics software tool evolution and the current status, to shed light on future directions and opportunities in this field. The present review explores new aspects of computational biology, including country partnerships, trends in technologies and area of development, research and development (R&D) investments and coding languages. This is the most comprehensive systematic overview of the field to date and provides the community with insights and knowledge on the direction of the development and evolution of bioinformatics software tools, highlighting the increasing complexity of analysis.
△ Less
Submitted 18 July, 2018;
originally announced July 2018.
-
Worst-case examples for Lasserre's measure--based hierarchy for polynomial optimization on the hypercube
Authors:
Etienne de Klerk,
Monique Laurent
Abstract:
We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], and a related hierarchy by De Klerk, Hess and Laurent [SIAM J. Optim. 27(1), (2017) pp. 347-367]. For polynomial optimization over the hypercube, we show a refined convergence analysis for the first hierarchy. We also show lower bounds…
▽ More
We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], and a related hierarchy by De Klerk, Hess and Laurent [SIAM J. Optim. 27(1), (2017) pp. 347-367]. For polynomial optimization over the hypercube, we show a refined convergence analysis for the first hierarchy. We also show lower bounds on the convergence rate for both hierarchies on a class of examples. These lower bounds match the upper bounds and thus establish the true rate of convergence on these examples. Interestingly, these convergence rates are determined by the distribution of extremal zeroes of certain families of orthogonal polynomials.
△ Less
Submitted 16 April, 2018;
originally announced April 2018.
-
The scaling properties and the multiple derivative of Legendre polynomials
Authors:
Guillaume Marc Laurent,
Geoffrey Robert Harrison
Abstract:
In this paper, we study the scaling properties of Legendre polynomials Pn(x). We show that Pn(ax), where a is a constant, can be expanded as a sum of either Legendre polynomials Pn(x) or their multiple derivatives dkPn(x)/dxk, and we derive a general expression for the expansion coefficients. In addition, we demonstrate that the multiple derivative dkPn(x)/dxk can also be expressed as a sum of Leg…
▽ More
In this paper, we study the scaling properties of Legendre polynomials Pn(x). We show that Pn(ax), where a is a constant, can be expanded as a sum of either Legendre polynomials Pn(x) or their multiple derivatives dkPn(x)/dxk, and we derive a general expression for the expansion coefficients. In addition, we demonstrate that the multiple derivative dkPn(x)/dxk can also be expressed as a sum of Legendre polynomials and we obtain a recurrence relation for the coefficients.
△ Less
Submitted 28 October, 2017;
originally announced November 2017.
-
Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
Authors:
Sander Gribling,
David de Laat,
Monique Laurent
Abstract:
In this paper we study bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. We construct a hierarchy of semidefinite programming lower bounds on the minimal entanglement dimension of a bipartite correlation. This hierarchy converges to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to rep…
▽ More
In this paper we study bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. We construct a hierarchy of semidefinite programming lower bounds on the minimal entanglement dimension of a bipartite correlation. This hierarchy converges to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum correlation when access to shared randomness is free. For synchronous correlations, we show a correspondence between the minimal entanglement dimension and the completely positive semidefinite rank of an associated matrix. We then study optimization over the set of synchronous correlations by investigating quantum graph parameters. We unify existing bounds on the quantum chromatic number and the quantum stability number by placing them in the framework of tracial optimization. In particular, we show that the projective packing number, the projective rank, and the tracial rank arise naturally when considering tracial analogues of the Lasserre hierarchy for the stability and chromatic number of a graph. We also introduce semidefinite programming hierarchies converging to the commuting quantum chromatic number and commuting quantum stability number.
△ Less
Submitted 9 January, 2018; v1 submitted 31 August, 2017;
originally announced August 2017.
-
Serverless Protocols for Inventory and Tracking with a UAV
Authors:
Collins Mtita,
Maryline Laurent,
Damien Sauveron,
Raja Naeem Akram,
Konstantinos Markantonakis,
Serge Chaumette
Abstract:
It is widely acknowledged that the proliferation of Unmanned Aerial Vehicles (UAVs) may lead to serious concerns regarding avionics safety, particularly when end-users are not adhering to air safety regulations. There are, however, domains in which UAVs may help to increase the safety of airplanes and the management of flights and airport resources that often require substantial human resources. F…
▽ More
It is widely acknowledged that the proliferation of Unmanned Aerial Vehicles (UAVs) may lead to serious concerns regarding avionics safety, particularly when end-users are not adhering to air safety regulations. There are, however, domains in which UAVs may help to increase the safety of airplanes and the management of flights and airport resources that often require substantial human resources. For instance, Paris Charles de Gaulle airport (CDG) has more than 7,000 staff and supports 30,000 direct jobs for more than 60 million passengers per year (as of 2016). Indeed, these new systems can be used beneficially for several purposes, even in sensitive areas like airports. Among the considered applications are those that suggest using UAVs to enhance safety of on-ground airplanes; for instance, by collecting (once the aircraft has landed) data recorded by different systems during the flight (like the sensors of the Aircraft Data Networks - ADN) or by examining the state of airplane structure. In this paper, our proposal is to use UAVs, under the control of the airport authorities, to inventory and track various tagged assets, such as luggage, supplies required for the flights, and maintenance tools. The aim of our proposal is to make airport management systems more efficient for operations requiring inventory and tracking, along with increasing safety (sensitive assets such as refueling tanks, or sensitive pieces of luggage can be tracked), thus raising financial profit.
△ Less
Submitted 17 August, 2017;
originally announced August 2017.
-
Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
Authors:
Sander Gribling,
David de Laat,
Monique Laurent
Abstract:
We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our…
▽ More
We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our hierarchies, compare them extensively to known lower bounds, and provide some (numerical) examples.
△ Less
Submitted 5 November, 2018; v1 submitted 4 August, 2017;
originally announced August 2017.
-
On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs
Authors:
Hao Hu,
Monique Laurent
Abstract:
We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extensio…
▽ More
We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph $G$ depending linearly on the size of $G$ and involving the depth of a decomposition tree of $G$ in terms of basic perfect graphs.
△ Less
Submitted 17 June, 2017;
originally announced June 2017.
-
New CAST Limit on the Axion-Photon Interaction
Authors:
CAST collaboration,
V. Anastassopoulos,
S. Aune,
K. Barth,
A. Belov,
H. Brauninger,
G. Cantatore,
J. M. Carmona,
J. F. Castel,
S. A. Cetin,
F. Christensen,
J. I. Collar,
T. Dafni,
M. Davenport,
T. A. Decker,
A. Dermenev,
K. Desch,
C. Eleftheriadis,
G. Fanourakis,
E. Ferrer-Ribas,
H. Fischer,
J. A. Garcia,
A. Gardikiotis,
J. G. Garza,
E. N. Gazis
, et al. (42 additional authors not shown)
Abstract:
During 2003--2015, the CERN Axion Solar Telescope (CAST) has searched for $a\toγ$ conversion in the 9 T magnetic field of a refurbished LHC test magnet that can be directed toward the Sun. In its final phase of solar axion searches (2013--2015), CAST has returned to evacuated magnet pipes, which is optimal for small axion masses. The absence of a significant signal above background provides a worl…
▽ More
During 2003--2015, the CERN Axion Solar Telescope (CAST) has searched for $a\toγ$ conversion in the 9 T magnetic field of a refurbished LHC test magnet that can be directed toward the Sun. In its final phase of solar axion searches (2013--2015), CAST has returned to evacuated magnet pipes, which is optimal for small axion masses. The absence of a significant signal above background provides a world leading limit of $g_{aγ} < 0.66 \times 10^{-10} {\rm GeV}^{-1}$ (95% C.L.) on the axion-photon coupling strength for $m_a \lesssim 0.02$ eV. Compared with the first vacuum phase (2003--2004), the sensitivity was vastly increased with low-background x-ray detectors and a new x-ray telescope. These innovations also serve as pathfinders for a possible next-generation axion helioscope.
△ Less
Submitted 20 December, 2017; v1 submitted 5 May, 2017;
originally announced May 2017.