Search

We show that for every first-order logic (FO) formula $\varphi$, and every graph class $\mathcal{G}$ of bounded expansion, there exists a distributed (deterministic) algorithm that, for every $n$-node graph $G\in\mathcal{G}$ of diameter $D$, decides whether $G\models \varphi$ in $O(D+\log n)$ rounds under the standard CONGEST model. Graphs of bounded expansion encompass many classes of sparse graphs such as planar graphs, bounded-treedepth graphs, bounded-treewidth graphs, bounded-degree graphs, and graphs excluding a fixed graph $H$ as a minor or topological minor. Note that our algorithm is optimal up to a logarithmic additional term, as even a simple FO formula such as "there are two vertices of degree 3" already on trees requires $\Omega(D)$ rounds in CONGEST. Our result extends to solving optimization problems expressed in FO (e.g., $k$-vertex cover of minimum weight), as well as to counting the number of solutions of a problem expressible in a fragment of FO (e.g., counting triangles), still running in $O(D+\log n)$ rounds under the CONGEST model. This exemplifies the contrast between sparse graphs and general graphs as far as CONGEST algorithms are concerned. For instance, Drucker, Kuhn, and Oshman [PODC 2014] showed that the problem of deciding whether a general graph contains a 4-cycle requires $\Theta(\sqrt{n}/\log n)$ rounds in CONGEST. For counting triangles, the best known algorithm of Chang, Pettie, and Zhang [SODA 2019] takes $\tilde{O}(\sqrt{n})$ rounds. Finally, our result extends to distributed certification. We show that, for every FO formula~$\varphi$, and every graph class of bounded expansion, there exists a certification scheme for $\varphi$ using certificates on $O(\log n)$ bits. This significantly generalizes the recent result of Feuilloley, Bousquet, and Pierron [PODC 2022], which held solely for graphs of bounded treedepth.

An extreme yet reconfigurable nonlinear response to a single photon by a photonic system is crucial for realizing a universal two-photon gate, an elementary building block for photonic quantum computing. Yet such a response, characterized by the photon blockade effect, has only been achieved in atomic systems or solid states ones that are difficult to scale up. Here we demonstrate electrically tunable partial photon blockade in dipolar waveguide polaritons on a semiconductor chip, measured via photon-correlations. Remarkably, these "dipolar photons" display a two-orders-of-magnitude stronger nonlinearity compared to unpolarized polaritons, with an extracted dipolar blockade radius up to more than 4 $\mu$m, significantly larger than the optical wavelength, and comparable to that of atomic Rydberg polaritons. Furthermore, we show that the dipolar interaction can be electrically switched and locally configured by simply tuning the gate voltage. Finally we show that with a simple modification of the design, a full photon blockade is expected, setting a new route towards scalable, reconfigurable, chip-integrated quantum photonic circuits with strong two-photon nonlinearities., Comment: 30 pages, 11 figures

The original proposal of quantum key distribution (QKD) was based on ideal single photon sources, which 40 years later, are still challenging to develop. Therefore, the development of decoy state protocols using weak coherent states (WCS) from lasers, set the frontier in terms of secure key rates. Here, we propose and experimentally emulate two simple-to-implement protocols that allow practical, far from ideal sub-Poissonian photon sources to outperform state-of-the-art WCS. By engineering the photon statistics of a quantum dot's biexciton-exciton cascade, we show that either a truncated decoy state protocol or a heralded purification protocol can be employed to achieve a significantly increased performance in terms of the maximal allowed channel loss for secure key creation, which can exceed that of WCS by more than 3dB. We then show that our recently demonstrated room temperature single photon sources, based on giant colloidal quantum dots coupled to nano-antennas, are already well within the optimal performance range. These protocols can be utilized efficiently on a host of various sub-Poissonian quantum emitters having controllable photon statistics, offering a practical approach to QKD without the hindering requirements on the single photon purity of the photon source.

In this note, we propose a novel approach for a class of autonomous dynamical systems that allows, given some observations of the solutions, to identify its parameters and reconstruct the state vector. This approach relies on proving the linear independence between some functions depending on the observations and its derivatives. In particular, we show that, in some cases, only low-order derivatives are necessary, opposed to classical approaches that need more derivation. We also provide different constructive procedures to retrieve the unknowns, which are based on the resolution of some linear systems. Moreover, under some analytic conditions, these unknowns may be retrieved with very few data. We finally apply this approach to some illustrative examples.

For $(\lambda_{1},...,\lambda_{d})=\lambda\in(0,1)^{d}$ with $\lambda_{1}>...>\lambda_{d}$, denote by $\mu_{\lambda}$ the Bernoulli convolution associated to $\lambda$. That is, $\mu_{\lambda}$ is the distribution of the random vector $\sum_{n\ge0}\pm\left(\lambda_{1}^{n},...,\lambda_{d}^{n}\right)$, where the $\pm$ signs are chosen independently and with equal weight. Assuming for each $1\le j\le d$ that $\lambda_{j}$ is not a root of a polynomial with coefficients $\pm1,0$, we prove that the dimension of $\mu_{\lambda}$ equals $\min\left\{ \dim_{L}\mu_{\lambda},d\right\} $, where $\dim_{L}\mu_{\lambda}$ is the Lyapunov dimension. More generally, we obtain this result in the context of homogeneous diagonal self-affine systems on $\mathbb{R}^{d}$ with rational translations. The proof extends to higher dimensions the works of Breuillard and Varj\'u and Varj\'u regarding Bernoulli convolutions on the real line. The main novelty and contribution of the present work lies in an extension of an entropy increase result, due to Varj\'u, in which the amount of increase in entropy is given explicitly. The extension of this result to the higher-dimensional non-conformal case requires significant new ideas., Comment: 31 pages

High-dimensional quantum key distribution (HDQKD) is a promising avenue to address the inherent limitations of basic QKD protocols. However, experimental realizations of HDQKD to date have relied on indeterministic photon sources that limit the achievable key rate. In this paper, we demonstrate a full emulation of a HDQKD system using a single colloidal giant quantum dot (gQD) as a deterministic, compact and room-temperature single-photon source (SPS). We demonstrate a practical protocol by encoding information in a high-dimensional space ($d = 3$) of the orbital angular momentum of the photons. Our experimental configuration incorporates two spatial light modulators for encoding and decoding the spatial information carried by individual photons. Our experimental demonstration establishes the feasibility of utilizing high radiative quantum yield gQDs as practical SPSs for HDQKD. We also demonstrate experimentally secure qudit transmission exceeding one secure bit per photon, thus already beating the traditional d=2 QKD capacity.

We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowledge, this marks the first meta-theorem regarding distributed model-checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph $G$ has a clique of size $k$, whether it admits a coloring with $k$ colors, whether it contains a graph $H$ as a subgraph or minor, or whether terminal vertices in $G$ could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. [PODC 2022], which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.

OLIMPO is a proposed Antarctic balloon-borne Sunyaev-Zel'dovich effect (SZE) imager to study gas dynamics associated with structure formation along with the properties of the warm-hot intergalactic medium (WHIM) residing in the connective filaments. During a 25 day flight OLIMPO will image a total of 10 z~0.05 galaxy clusters and 8 bridges at 145, 250, 365, and 460 GHz at an angular resolution of 1.0'-3.3'. The maps will be significantly deeper than those planned from CMB-S4 and CCAT-P, and will have excellent fidelity to the large angular scales of our low-z targets, which are difficult to probe from the ground. In combination with X-ray data from eROSITA and XRISM we will transform our current static view of galaxy clusters into a full dynamic picture by measuring the internal intra-cluster medium (ICM) velocity structure with the kinematic SZE, X-ray spectroscopy, and the power spectrum of ICM fluctuations. Radio observations from ASKAP and MeerKAT will be used to better understand the connection between ICM turbulence and shocks with the relativistic plasma. Beyond the cluster boundary, we will combine thermal SZE maps from OLIMPO with X-ray imaging from eROSITA to measure the thermodynamics of the WHIM residing in filaments, providing a better understanding of its properties and its contribution to the total baryon budget., Comment: From the proceedings of the mm Universe 2023

To harness the potential of radially polarized single photons in applications such as high-dimensional quantum key distribution (HD-QKD) and quantum communication, we demonstrate an on-chip, room-temperature device, which generates highly directional radially polarized photons at very high rates. The photons are emitted from a giant CdSe/CdS colloidal quantum dot (gQD) accurately positioned at the tip of a metal nanocone centered inside a hybrid metal-dielectric bullseye antenna. We show that due to the large and selective Purcell enhancement specifically for the out-of-plane optical dipole of the gQD, the emitted photons can have a very high degree of radial polarization (>93%), based on a quantitative metric. Our study emphasizes the importance of accurate gQD positioning for optimal radial polarization purity through extensive experiments and simulations, which contribute to the fundamental understanding of radial polarization in nanostructured devices and pave the way for implementation of such systems in practical applications using structured quantum light.

We prove the following type of discrete entropy monotonicity for sums of isotropic, log-concave, independent and identically distributed random vectors $X_1,\dots,X_{n+1}$ on $\mathbb{Z}^d$: $$ H(X_1+\cdots+X_{n+1}) \geq H(X_1+\cdots+X_{n}) + \frac{d}{2}\log{\Bigl(\frac{n+1}{n}\Bigr)} +o(1), $$ where $o(1)$ vanishes as $H(X_1) \to \infty$. Moreover, for the $o(1)$-term, we obtain a rate of convergence $ O\Bigl({H(X_1)}{e^{-\frac{1}{d}H(X_1)}}\Bigr)$, where the implied constants depend on $d$ and $n$. This generalizes to $\mathbb{Z}^d$ the one-dimensional result of the second named author (2023). As in dimension one, our strategy is to establish that the discrete entropy $H(X_1+\cdots+X_{n})$ is close to the differential (continuous) entropy $h(X_1+U_1+\cdots+X_{n}+U_{n})$, where $U_1,\dots, U_n$ are independent and identically distributed uniform random vectors on $[0,1]^d$ and to apply the theorem of Artstein, Ball, Barthe and Naor (2004) on the monotonicity of differential entropy. In fact, we show this result under more general assumptions than log-concavity, which are preserved up to constants under convolution. In order to show that log-concave distributions satisfy our assumptions in dimension $d\ge2$, more involved tools from convex geometry are needed because a suitable position is required. We show that, for a log-concave function on $\mathbb{R}^d$ in isotropic position, its integral, barycenter and covariance matrix are close to their discrete counterparts. Moreover, in the log-concave case, we weaken the isotropicity assumption to what we call almost isotropicity. One of our technical tools is a discrete analogue to the upper bound on the isotropic constant of a log-concave function, which extends to dimensions $d\ge1$ a result of Bobkov, Marsiglietti and Melbourne (2022)., Comment: 26 pages, no figures. In the updated version we relax the hypotheses of the main theorems. Section 2 now has the proofs of the main results under the weaker assumptions and Section 3 is devoted to proving that log-concavity implies these new assumptions. Definition 2, Proposition 13 and Theorem 18 are new. The quantitative estimate in Lemma 14 has been improved from the previous version

Augustine et al. [DISC 2022] initiated the study of distributed graph algorithms in the presence of Byzantine nodes in the congested clique model. In this model, there is a set $B$ of Byzantine nodes, where $|B|$ is less than a third of the total number of nodes. These nodes have complete knowledge of the network and the state of other nodes, and they conspire to alter the output of the system. The authors addressed the connectivity problem, showing that it is solvable under the promise that either the subgraph induced by the honest nodes is connected, or the graph has $2|B|+1$ connected components. In the current work, we continue the study of the Byzantine congested clique model by considering the recognition of other graph properties, specifically \emph{hereditary properties}. A graph property is \emph{hereditary} if it is closed under taking induced subgraphs. Examples of hereditary properties include acyclicity, bipartiteness, planarity, and bounded (chromatic, independence) number, etc. For each class of graphs $\mathcal{G}$ satisfying an hereditary property (an hereditary graph-class), we propose a randomized algorithm which, with high probability, (1) accepts if the input graph $G$ belongs to $\mathcal{G}$, and (2) rejects if $G$ contains at least $|B| + 1$ disjoint subgraphs not belonging to $\mathcal{G}$. The round complexity of our algorithm is $$\mathcal{O}\left(\left(\dfrac{\log \left(\left|\mathcal{G}_n\right|\right)}{n} +|B|\right)\cdot\textrm{polylog}(n)\right),$$ where $\mathcal{G}_n$ is the set of $n$-node graphs in $\mathcal{G}$. Finally, we obtain an impossibility result that proves that our result is tight. Indeed, we consider the hereditary class of acyclic graphs, and we prove that there is no algorithm that can distinguish between a graph being acyclic and a graph having $|B|$ disjoint cycles.

In the Minimum Clique Routing Problem on Cycles \textsc{MCRPC} we are given a cycle together with a set of demands (weighted origin-destination pairs) and the goal is to route all the pairs minimizing the maximum weighted clique of the intersection graph induced by the routing. The vertices of this graph are the demands with their corresponding weights and two demands are adjacent when their routes share at least one arc. In this work we are not only interested in the \textsc{MCRPC} but also in two natural subproblems. First, we consider the situation where the demands are disjoint, in the sense that every two demands do not share any of their corresponding ends. Second, we analyze the subproblem where the weights of the routes are all equal. We first show that the problem is NP-complete even in the subproblem of disjoint demands. For the case of arbitrary weights, we exhibit a simple combinatorial 2-approximation algorithm and a $\frac{3}{2}$-approximation algorithm based on rounding a solution of a relaxation of an integer linear programming formulation of our problem. Finally, we give a Fixed Parameter Tractable algorithm for the case of uniform weights, whose parameter is related to the maximum degree of the intersection graph induced by any routing.

In the context of distributed certification, the recognition of graph classes has started to be intensively studied. For instance, different results related to the recognition of planar, bounded tree-width and $H$-minor free graphs have been recently obtained. The goal of the present work is to design compact certificates for the local recognition of relevant geometric intersection graph classes, namely interval, chordal, circular arc, trapezoid and permutation. More precisely, we give proof labeling schemes recognizing each of these classes with logarithmic-sized certificates. We also provide tight logarithmic lower bounds on the size of the certificates on the proof labeling schemes for the recognition of any of the aforementioned geometric intersection graph classes.

Let $\Phi:=\left\{ (x_{1},...,x_{d})\rightarrow\left(r_{i,1}x_{1}+a_{i,1},...,r_{i,d}x_{d}+a_{i,d}\right)\right\} _{i\in\Lambda}$ be an affine diagonal IFS on $\mathbb{R}^{d}$. Suppose that for each $1\le j_{1}

Electrically controlled photonic circuits hold promise for information technologies with greatly improved energy efficiency and quantum information processing capabilities. However, weak nonlinearity and electrical response of typical photonic materials have been two critical challenges. Therefore hybrid electronic-photonic systems, such as semiconductor exciton-polaritons, have been intensely investigated for their potential to allow higher nonlinearity and electrical control, with limited success so far. Here we demonstrate an electrically-gated waveguide architecture for dipolar-polaritons that allows enhanced and electrically-controllable polariton nonlinearities, enabling an electrically-tuned reflecting switch (mirror) and transistor of the dipolar-polaritons. The polariton transistor displays blockade and anti-blockade by compressing a dilute dipolar-polariton pulse exhibiting very strong dipolar interactions. The large nonlinearities are explained using a simple density-dependent polarization field that very effectively screens the external electric field, with an order of magnitude enhancement of the nonlinearities as compared to fixed dipoles. We project that a quantum blockade at the single polariton level is feasible in such a device., Comment: 12 pages, 6 figures, 1 table

A proof-labeling scheme (PLS) for a boolean predicate $\Pi$ on labeled graphs is a mechanism used for certifying the legality with respect to $\Pi$ of global network states in a distributed manner. In a PLS, a certificate is assigned to each processing node of the network, and the nodes are in charge of checking that the collection of certificates forms a global proof that the system is in a correct state, by exchanging the certificates once, between neighbors only. The main measure of complexity is the size of the certificates. Many PLSs have been designed for certifying specific predicates, including cycle-freeness, minimum-weight spanning tree, planarity, etc. In 2021, a breakthrough has been obtained, as a meta-theorem stating that a large set of properties have compact PLSs in a large class of networks. Namely, for every $\mathrm{MSO}_2$ property $\Pi$ on labeled graphs, there exists a PLS for $\Pi$ with $O(\log n)$-bit certificates for all graphs of bounded tree-depth. This result has been extended to the larger class of graphs with bounded {tree-width}, using certificates on $O(\log^2 n)$ bits. We extend this result even further, to the larger class of graphs with bounded clique-width, which, as opposed to the other two aforementioned classes, includes dense graphs. We show that, for every $\mathrm{MSO}_1$ property $\Pi$ on labeled graphs, there exists a PLS for $\Pi$ with $O(\log^2 n)$ bit certificates for all graphs of bounded clique-width.

Flare frequency distributions represent a key approach to addressing one of the largest problems in solar and stellar physics: determining the mechanism that counter-intuitively heats coronae to temperatures that are orders of magnitude hotter than the corresponding photospheres. It is widely accepted that the magnetic field is responsible for the heating, but there are two competing mechanisms that could explain it: nanoflares or Alfv\'en waves. To date, neither can be directly observed. Nanoflares are, by definition, extremely small, but their aggregate energy release could represent a substantial heating mechanism, presuming they are sufficiently abundant. One way to test this presumption is via the flare frequency distribution, which describes how often flares of various energies occur. If the slope of the power law fitting the flare frequency distribution is above a critical threshold, $\alpha=2$ as established in prior literature, then there should be a sufficient abundance of nanoflares to explain coronal heating. We performed $>$600 case studies of solar flares, made possible by an unprecedented number of data analysts via three semesters of an undergraduate physics laboratory course. This allowed us to include two crucial, but nontrivial, analysis methods: pre-flare baseline subtraction and computation of the flare energy, which requires determining flare start and stop times. We aggregated the results of these analyses into a statistical study to determine that $\alpha = 1.63 \pm 0.03$. This is below the critical threshold, suggesting that Alfv\'en waves are an important driver of coronal heating., Comment: 1,002 authors, 14 pages, 4 figures, 3 tables, published by The Astrophysical Journal on 2023-05-09, volume 948, page 71

We provide a duality result linking the value function for a control problem with supremum cost H under an isoperimetric inequality G $\le$ gmax, and the value function for the same controlled dynamics with cost G and state constraint H $\le$ hmax. This duality is proven for initial conditions at which lower semi-continuity of the value functions can be guaranteed, and is completed with optimality considerations. Furthermore, we provide structural assumptions on the dynamics under which such regularity can be established. As a by-product, we illustrate the partial equivalence between recentworks dealing with non-pharmaceutically controlled epidemics under peak or budget restrictions.

In this paper we establish new simple local geometric criteria for discrete entropic curvature introduced in [47] that are powerful enough to capture many geometric properties of complex models arising in mathematical physics. These results are robust in the sense that they apply to any discrete graph equipped with a Markov reversible generator. Our definitions of entropic curvature differ from the one of the pioneering works of Erbar-Maas [19,20] (which is already a discrete analog of the Lott-Sturm-Villani entropic curvature in the continuous setting). Singularly, our results provide refined concentration properties related to the celebrated convex-hull method by Talagrand [50,51] for a large class of probability measures that cannot be captured from Erbar- Maas entropic definition of curvature. Our approach gives also a new insight of the convex hull method, without being related to induction arguments. We illustrate the power of our results, as well as the general entropic strategy developed in this paper, to tackle challenging models studied in mathematical physics, including Gibbs measures with interaction potentials such as Ising models on the discrete hypercube and measures with interaction potential on the lattice $\mathbb{Z}^n$. For instance, we significantly improve the constant of the refined convex concentration properties obtained in [2] for Ising models. Moreover, when dealing with the antiferromagnetic Curie-Weiss model, we improve the previously known bound for entropic curvature by a factor of $\sqrt{n}$. Our simple criteria also provides the expected right order of magnitude $C/\sqrt n$ for the lower-bound on the entropic curvature for the renowned Sherrington-Kirkpatrick model from the spin glass theory. This last result is consistant with the recent works [6,17] on the modified logarithmic Sobolev and Poincar\'e inequalities for the Sherrington-Kirkpatrick model., Comment: 79 pages. New introduction and reorganization of sections

We demonstrate an important step towards on chip integration of single photon sources operating at room temperature fiber coupling of a directional quantum emitter with back-excitation. Directionality is achieved with a hybrid metal-dielectric bullseye antenna, while back-excitation is permitted by placement of the emitter at or in a sub-wavelength hole positioned at the bullseye center. Overall, the unique design enables a direct laser excitation from the back of the on-chip device and very efficient coupling of the highly collimated photon emission to either low numerical aperture (NA) free space optics or directly to an optical fiber from the front. To show the versatility of the concept, we fabricate devices containing either a colloidal quantum dot or a silicon-vacancy center containing nanodiamond, which are accurately coupled to the nano-antenna using two different nano-positioning methods. Both back-excited devices display front collection efficiencies of about 70 % at NAs as low as 0.5. Moreover, the combination of back-excitation with forward low-NA directionality enables direct coupling of the emitted photons into a proximal optical fiber without the need of any coupling optics, thereby facilitating and greatly simplifying future integration.

For a particular class of planar dynamics that are linear with respect to the control variable, we show that the feedback strategy ''null-singular null'' is minimizing the maximum of a coordinate over infinite horizon, under a L 1 budget constraint on the control. Moreover, we characterize the optimal cost as a function of the budget. The proof is based on an unusual use of the clock form. This result generalizes the one obtained formerly for the SIR epidemiological model to more general Kolmogorov dynamics, that we illustrate on other biological models.

We study the design of energy-efficient algorithms for the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or over all the nodes, of the number of rounds at which an edge, or a node, is active in the algorithm. We first show that every Turing-computable problem has a CONGEST algorithm with constant node-activation complexity, and therefore constant edge-activation complexity as well. That is, every node (resp., edge) is active in sending (resp., transmitting) messages for only $O(1)$ rounds during the whole execution of the algorithm. In other words, every Turing-computable problem can be solved by an algorithm consuming the least possible energy. In the LOCAL model, the same holds obviously, but with the additional feature that the algorithm runs in $O(\mbox{poly}(n))$ rounds in $n$-node networks. However, we show that insisting on algorithms running in $O(\mbox{poly}(n))$ rounds in the CONGEST model comes with a severe cost in terms of energy. Namely, there are problems requiring $\Omega(\mbox{poly}(n))$ edge-activations (and thus $\Omega(\mbox{poly}(n))$ node-activations as well) in the CONGEST model whenever solved by algorithms bounded to run in $O(\mbox{poly}(n))$ rounds. Finally, we demonstrate the existence of a sharp separation between the edge-activation complexity and the node-activation complexity in the CONGEST model, for algorithms bounded to run in $O(\mbox{poly}(n))$ rounds. Specifically, under this constraint, there is a problem with $O(1)$ edge-activation complexity but $\tilde{\Omega}(n^{1/4})$ node-activation complexity.

Let $\mu$ be a self-affine measure on $\mathbb{R}^{d}$ associated to an affine IFS $\Phi$ and a positive probability vector $p$. Suppose that the maps in $\Phi$ do not have a common fixed point, and that standard irreducibility and proximality assumptions are satisfied by their linear parts. We show that $\dim\mu$ is equal to the Lyapunov dimension $\dim_{L}(\Phi,p)$ whenever $d=3$ and $\Phi$ satisfies the strong separation condition (or the milder strong open set condition). This follows from a general criteria ensuring $\dim\mu=\min\{d,\dim_{L}(\Phi,p)\}$, from which earlier results in the planar case also follow. Additionally, we prove that $\dim\mu=d$ whenever $\Phi$ is Diophantine (which holds e.g. when $\Phi$ is defined by algebraic parameters) and the entropy of the random walk generated by $\Phi$ and $p$ is at least $(\chi_{1}-\chi_{d})\frac{(d-1)(d-2)}{2}-\sum_{k=1}^{d}\chi_{k}$, where $0>\chi_{1}\ge...\ge\chi_{d}$ are the Lyapunov exponents. We also obtain results regarding the dimension of orthogonal projections of $\mu$., Comment: 89 pages

We consider a two-patches SIR model where communication occurs thru commuters, distinguishing explicitly permanently resident populations from commuters populations. We give an explicit formula of the reproduction number, and show how the proportions of permanently resident populations impact it. We exhibit non-intuitive situations for which allowing commuting from a safe territory to another one where the transmission rate is higher can reduce the overall epidemic threshold and avoid an outbreak.

As properties of mono- to few layers of exfoliated van der Waals heterostructures are heavily dependent on their thicknesses, accurate thickness measurement becomes imperative in their study. Commonly used atomic force microscopy and Raman spectroscopy techniques may be invasive and produce inconclusive results. Alternatively, spectroscopic ellipsometry is limited by tens-of-microns lateral resolution and/or low data acquisition rates, inhibiting its utilization for micro-scale exfoliated flakes. In this work, we demonstrate a Fourier imaging spectroscopic micro-ellipsometer with sub-5 microns lateral resolution along with fast data acquisition rate and present angstrom-level accurate and consistent thickness mapping on mono-, bi- and trilayers of graphene, hexagonal boron nitride and transition metal dichalcogenide (MoS2, WS2, MoSe2, WSe2) flakes. We show that the optical microscope integrated ellipsometer can also map minute thickness variations over a micro-scale flake. In addition, our system addresses the pertinent issue of identifying monolayer thick hBN.

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector $x\in\{0,1\}^n$ together with an index $i\in[n]$, Bob is given a binary vector $y\in\{0,1\}^n$ together with an index $j\in[n]$, and, after a single round of 2-way communication, Alice must output a boolean $\textrm{out}_A$, and Bob must output a boolean $\textrm{out}_B$, such that $\mbox{out}_A\land\mbox{out}_B = x_j\oplus y_i$. We show that the communication complexity of XOR-Index is $\Omega(n)$ bits.

Spectroscopic ellipsometry is a widely used optical technique both in industry and research for determining the optical properties and thickness of thin films. The effective use of spectroscopic ellipsometry on micro-structures is inhibited by technical limitations on lateral resolution and data acquisition rate. Here we introduce a spectroscopic micro-ellipsometer (SME), capable of measuring spectrally resolved ellipsometric data at many angles of incidence in a single-shot with a lateral resolution down to 2 microns. The SME can be easily integrated into generic optical microscopes by addition of a few stock optics. We demonstrate complex refractive index and thickness measurements by the SME which are in excellent agreement with a commercial spectroscopic ellipsometer. As an application for its accuracy and high lateral resolution, the SME can characterize the optical properties and number of layers of exfoliated transition-metal dichalcogenides and graphene, for structures that are a few microns in size.

We give the explicit solution of the optimal control problem which consists in minimizing the epidemic peak in the SIR model when the control is an attenuation factor of the infectious rate, subject to a L 1 budget constraint. The optimal strategy is given as a feedback control which consists in an singular arc maintaining the infected population at a constant level until the immunity threshold is reached, and no intervention outside the singular arc.

We revisit the optimal control problem with maximum cost with the objective to provide different equivalent reformulations suitable to numerical methods. We propose two reformulations in terms of extended Mayer problems with constraint, and another one in terms of a differential inclusion with upper-semi continuous right member but without constraint. For this last one we also propose an approximation scheme of the optimal value from below. These approaches are illustrated and discussed on several examples.

Layered bosonic dipolar fluids have been suggested to host a condensate of interlayer molecular bound states. However, its experimental observation has remained elusive. Motivated by two recent experimental works [Hubert et al., Phys. Rev. X 9, 021026 (2019) and D. J. Choksy et al., Phys. Rev. B 103 045126 (2021)], we theoretically study, using numerically exact quantum Monte Carlo calculations, the experimental signatures of collective interlayer pairing in vertically stacked indirect exciton (IX) layers. We find that IX energy shifts associated with each layer evolve non trivially as a function of density imbalance following a nonmonotonic trend with a jump discontinuity at density balance, identified with the interlayer IX molecule gap. This behavior discriminates between the superfluidity of interlayer bound pairs and independent dipole condensation in distinct layers. Considering finite temperature and finite density imbalance conditions, we find a cascade of Berezinskii--Kosterlitz--Thouless (BKT) transitions, initially into a pair superfluid and only then, at lower temperatures, into complete superfluidity of both layers. Our results may provide a theoretical interpretation of existing experimental observations in GaAs double quantum well (DQW) bilayer structures. Furthermore, to optimize the visibility of pairing dynamics in future studies, we present an analysis suggesting realistic experimental settings in GaAs and transition metal dichalcogenide (TMD) bilayer DQW heterostructures where collective interlayer pairing and pair superfluidity can be clearly observed., Comment: Published version

A graph $G=(V,E)$ is a geometric intersection graph if every node $v \in V$ is identified with a geometric object of some particular type, and two nodes are adjacent if the corresponding objects intersect. Geometric intersection graph classes have been studied from both the theoretical and practical point of view. On the one hand, many hard problems can be efficiently solved or approximated when the input graph is restricted to a geometric intersection class of graphs. On the other hand, these graphs appear naturally in many applications such as sensor networks, scheduling problems, and others. Recently, in the context of distributed certification and distributed interactive proofs, the recognition of graph classes has started to be intensively studied. Different results related to the recognition of trees, bipartite graphs, bounded diameter graphs, triangle-free graphs, planar graphs, bounded genus graphs, $H$-minor free graphs, etc., have been obtained. The goal of the present work is to design efficient distributed protocols for the recognition of relevant geometric intersection graph classes, namely permutation graphs, trapezoid graphs, circle graphs, and polygon-circle graphs. More precisely, for the two first classes, we give proof labeling schemes recognizing them with logarithmic-sized certificates. For the other two classes, we give three-round distributed interactive protocols that use messages and certificates of size $\mathcal{O}(\log n)$. Finally, we provide logarithmic lower-bounds on the size of the certificates on the proof labeling schemes for the recognition of any of the aforementioned geometric intersection graph classes.

Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two properties are satisfied: completeness, i.e., for every legal instance, there is a certificate assignment leading all processes to accept, and soundness, i.e., for every illegal instance, and for every certificate assignment, at least one process rejects. The verification of the certificates must be fast, and the certificates themselves must be small. A large quantity of results have been produced in this framework, each aiming at designing a distributed certification mechanism for specific boolean predicates. This paper presents a "meta-theorem", applying to many boolean predicates at once. Specifically, we prove that, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs, there exists a distributed certification mechanism using certificates on $O(\log^2n)$ bits in $n$-node graphs of bounded treewidth, with a verification protocol involving a single round of communication between neighbors.

We optimize a general model of bioprocesses, which is nonconvex due to the microbial growth in the biochemical reactors. We formulate a convex relaxation and give conditions guaranteeing its exactness in both the transient and steady state cases. When the growth kinetics are modeled by the Monod function under constant biomass or the Contois function, the relaxation is a second-order cone program, which can be solved efficiently at large scales. We implement the model on a numerical example based on a wastewater treatment system.

We establish a complete algebraic characterization of self-similar iterated function systems $\Phi$ on $\mathbb{R}^{d}$, for which there exists a positive probability vector $p$ so that the Fourier transform of the self-similar measure corresponding to $\Phi$ and $p$ does not tend to $0$ at infinity., Comment: 41 pages, some minor changes to the introduction

We analyze the identifiability and observability of the well-known SIR epidemic model with an additional compartment Q of the sub-population of infected individuals that are placed in quarantine (SIQR model), considering that the flow of individuals placed in quarantine and the size of the quarantine population are known at any time. Then, we focus on the problem of identification of the model parameters, with the synthesis of an observer.

We maximize the production of biogas in a gradostat at steady state. The physical decision variables are the water, substrate, and biomass entering each tank and the flows through the interconnecting pipes. Our main technical focus is the nonconvex constraint describing microbial growth. We formulate a relaxation and prove that it is exact when the gradostat is outflow connected, its system matrix is irreducible, and the growth rate satisfies a simple condition. The relaxation has second-order cone representations for the Monod and Contois growth rates. We extend the steady state models to the case of multiple time periods by replacing the derivatives with numerical approximations instead of setting them to zero. The resulting optimizations are second-order cone programs, which can be solved at large scales using standard industrial software.

Coherent exchange of single photons is at the heart of applied Quantum Optics. The negatively-charged silicon vacancy center in diamond is among most promising sources for coherent single photons. Its large Debye-Waller factor, short lifetime and extraordinary spectral stability is unique in the field of solid-state single photon sources. However, the excitation and detection of individual centers requires high numerical aperture optics which, combined with the need for cryogenic temperatures, puts technical overhead on experimental realizations. Here, we investigate a hybrid quantum photonics platform based on silicon-vacancy center in nanodiamonds and metallic bullseye antenna to realize a coherent single-photon interface that operates efficiently down to low numerical aperture optics with an inherent resistance to misalignment.

We present compact distributed interactive proofs for the recognition of two important graph classes, well-studied in the context of centralized algorithms, namely complement reducible graphs and distance-hereditary graphs. Complement reducible graphs (also called cographs) are defined as the graphs not containing a four-node path $P_4$ as an induced subgraph. Distance-hereditary graphs are a super-class of cographs, defined as the graphs where the distance (shortest paths) between any pair of vertices is the same on every induced connected subgraph. First, we show that there exists a distributed interactive proof for the recognition of cographs with two rounds of interaction. More precisely, we give a $\mathsf{dAM}$ protocol with a proof size of $\mathcal{O}(\log n)$ bits that uses shared randomness and recognizes cographs with high probability. Moreover, our protocol can be adapted to verify any Turing-decidable predicate restricted to cographs in $\mathsf{dAM}$ with certificates of size $\mathcal{O}(\log n)$. Second, we give a three-round, $\mathsf{dMAM}$ interactive protocol for the recognition of distance-hereditary graphs, still with a proof size of $\mathcal{O}(\log n)$ bits and also using shared randomness. Finally, we show that any one-round (denoted $\mathsf{dM}$) or two-round, $\mathsf{dMA}$ protocol for the recognition of cographs or distance-hereditary graphs requires certificates of size $\Omega(\log n)$ bits. Moreover, we show that any constant-round $\mathsf{dAM}$ protocol using shared randomness requires certificates of size $\Omega(\log \log n)$., Comment: 20 pages, 6 figures

In this review, we recall the concepts of Identifiability and Observability of dynamical systems, and analyse them in the framework of Mathematical Epidemiology. We show that, even for simple and well known models of the literature, these properties are not always fulfilled. We then consider the problem of practical identifiability and observability, which are connected to sensitivity and numerical condition numbers. We also recall the concept of observers to reconstruct state variable of the model which are not observed, and show how it can used with epidemiological models.

Deterministic GHz-rate single photon sources at room-temperature would be essential components for various quantum applications. However, both the slow intrinsic decay rate and the omnidirectional emission of typical quantum emitters are two obstacles towards achieving such a goal which are hard to overcome simultaneously. Here we solve this challenge by a hybrid approach, using a complex monolithic photonic resonator constructed of a gold nanocone responsible for the rate enhancement, and a circular Bragg antenna for emission directionality. A repeatable process accurately binds quantum dots to the tip of the antenna-embedded nanocone. As a result we achieve simultaneous 20-fold emission rate enhancement and record-high directionality leading to an increase in the observed brightness by a factor as large as 580 (120) into an NA = 0.22 (0.5). We project that such miniaturized on-chip devices can reach photon rates approaching 2.3*10^8 single photons/second thus enabling ultra-fast light-matter interfaces for quantum technologies at ambient conditions.

Large content providers and content distribution network operators usually connect with large Internet service providers (eyeball networks) through dedicated private peering. The capacity of these private network interconnects is provisioned to match the volume of the real content demand by the users. Unfortunately, in case of a surge in traffic demand, for example due to a content trending in a certain country, the capacity of the private interconnect may deplete and the content provider/distributor would have to reroute the excess traffic through transit providers. Although, such overflow events are rare, they have significant negative impacts on content providers, Internet service providers, and end-users. These include unexpected delays and disruptions reducing the user experience quality, as well as direct costs paid by the Internet service provider to the transit providers. If the traffic overflow events could be predicted, the Internet service providers would be able to influence the routes chosen for the excess traffic to reduce the costs and increase user experience quality. In this article we propose a method based on an ensemble of deep learning models to predict overflow events over a short term horizon of 2-6 hours and predict the specific interconnections that will ingress the overflow traffic. The method was evaluated with 2.5 years' traffic measurement data from a large European Internet service provider resulting in a true-positive rate of 0.8 while maintaining a 0.05 false-positive rate. The lockdown imposed by the COVID-19 pandemic reduced the overflow prediction accuracy. Nevertheless, starting from the end of April 2020 with the gradual lockdown release, the old models trained before the pandemic perform equally well.

We study the dimension of self-similar measures associated to a homogeneous iterated function system of three contracting similarities on $\bf R$ and other more general IFS's. We extend some of the theory recently developed for Bernoulli convolutions to this setting. In the setting of three maps a new phenomenon occurs, which has been highlighted by recent examples of Baker, and B\'ar\'any, K\"aenm\"aki. To overcome the difficulties stemming form these, we develop novel techniques, including an extension of Hochman's entropy increase method to a function field setup., Comment: 85 pages, minor revision based on referee's report, final accepted version to appear in Duke Math. J

Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a $\mathsf{dMAM}(O(\log n))$ protocol for this class, that is, a distributed interactive protocol with $O(\log n)$-bit proof size in $n$-node graphs, and three interactions between the (centralizer) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a $\mathsf{dMAM}(O(\log n))$ protocol for the class of planar graphs, as well as for the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of $O(\log n)$ bits. This result also holds for the class of graphs with bounded demi-genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded demigenus.

Assuming strong irreducibility and proximality, we prove that the Furstenberg measure, corresponding to a finitely supported measure on the general linear group of a finite dimensional real vector space, is exact dimensional. We also establish a Ledrappier-Young type formula for its dimension. The general strategy of the proof is based on the argument given by Feng for the exact dimensionality of self-affine measures., Comment: 43 pages

In distributed interactive proofs, the nodes of a graph G interact with a powerful but untrustable prover who tries to convince them, in a small number of rounds and through short messages, that G satisfies some property. This series of interactions is followed by a phase of distributed verification, which may be either deterministic or randomized, where nodes exchange messages with their neighbors. The nature of this last verification round defines the two types of interactive protocols. We say that the protocol is of Arthur-Merlin type if the verification round is deterministic. We say that the protocol is of Merlin-Arthur type if, in the verification round, the nodes are allowed to use a fresh set of random bits. In the original model introduced by Kol, Oshman, and Saxena [PODC 2018], the randomness was private in the sense that each node had only access to an individual source of random coins. Crescenzi, Fraigniaud, and Paz [DISC 2019] initiated the study of the impact of shared randomness (the situation where the coin tosses are visible to all nodes) in the distributed interactive model. In this work, we continue that research line by showing that the impact of the two forms of randomness is very different depending on whether we are considering Arthur-Merlin protocols or Merlin-Arthur protocols. While private randomness gives more power to the first type of protocols, shared randomness provides more power to the second. Our results also connect shared randomness in distributed interactive proofs with distributed verification, and new lower bounds are obtained.

Deterministic coupling between photonic nodes in a quantum network is an essential step towards implementing various quantum technologies. The omnidirectionality of free-standing emitters, however, makes this coupling highly inefficient, in particular if the distant nodes are coupled via low numerical aperture (NA) channels such as optical fibers. This limitation requires placing quantum emitters in nanoantennas that can direct the photons into the channels with very high efficiency. Moreover, to be able to scale such technologies to a large number of channels, the placing of the emitters should be deterministic. In this work we present a method for directly locating single free-standing quantum emitters with high spatial accuracy at the center of highly directional bullseye metal-dielectric nanoantennas. We further employ non-blinking, high quantum yield colloidal quantum dots (QDs) for on-demand single-photon emission that is uncompromised by instabilities or non-radiative exciton recombination processes. Taken together this approach results in a record-high collection efficiency of 85% of the single photons into a low NA of 0.5, setting the stage for efficient coupling between on-chip, room temperature nanoantenna-emitter devices and a fiber or a remote free-space node without the need for additional optics.

Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a \emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a \dMAM\/ protocol), and uses small certificates, on $O(\log n)$ bits in $n$-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a \emph{proof-labeling scheme} for planarity, still using certificates on just $O(\log n)$ bits. We also show that there are no proof-labeling schemes -- in fact, even no \emph{locally checkable proofs} -- for planarity using certificates on $o(\log n)$ bits., Comment: To appear at PODC 2020

We determine the zero temeperature phase diagram of excitons in the symmetric transition-metal dichalcogenide tri-layer heterosctructure WSe2/MoSe2/WSe2. First principle calculations reveal two distinct types of interlayer excitonic states, a lower energy symmetric quadrupole and a higher energy asymmetric dipole. While interaction between quadrupolar excitons is always repulsive, anti-parallel dipolar excitons attract at large distances. We find quantum phase transitions between a repulsive quadrupole lattice phase and a staggered (anti-parallel) dipolar lattice phase, driven by the competition between the exciton-exciton interactions and the single exciton energies. Remarkably, the intrinsic nature of each interlayer exciton is completely different in each phase. This is a striking example for the possible rich quantum physics in a system where the single particle properties and the many-body state are dynamically coupled through the particle interactions.

A previous study of MD algorithms designed for GPU use is extended to cover more recent developments in GPU architecture. Algorithm modifications are described, together with extensions to more complex systems. New measurements include the effects of increased parallelism on GPU performance, as well as comparisons with multiple-core CPUs using multitasking based on CPU threads and message passing. The results show that the GPU retains a significant performance advantage., Comment: 10 pages

We establish the exact overlaps conjecture for iterated functions systems on the real line with algebraic contractions and arbitrary translations., Comment: Some minor changes to the introduction