Search

In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an $m$-edge graph $G = (V, E)$ that is a $\Phi$-expander, i.e. where $\lvert \partial S \rvert \geq \Phi \cdot \mathrm{vol}(S)$ for every $S \subseteq V, \mathrm{vol}(S) \leq \mathrm{vol}(V)/2$. Beyond its simplicity and structural importance, this question is well-motivated by the current state-of-the-art of fast algorithms for $\ell_{\infty}$ oblivious routings that reduce to the expander-case which is in turn solved by electrical flow routing. Our main result proves that the electrical routing is an $O(\Phi^{-1} \log m)$-competitive oblivious routing in the $\ell_1$- and $\ell_\infty$-norms. We further observe that the oblivious routing is $O(\log^2 m)$-competitive in the $\ell_2$-norm and, in fact, $O(\log m)$-competitive if $\ell_2$-localization is $O(\log m)$ which is widely believed. Using these three upper bounds, we can smoothly interpolate to obtain upper bounds for every $p \in [2, \infty]$ and $q$ given by $1/p + 1/q = 1$. Assuming $\ell_2$-localization in $O(\log m)$, we obtain that in $\ell_p$ and $\ell_q$, the electrical oblivious routing is $O(\Phi^{-(1-2/p)}\log m)$ competitive. Using the currently known result for $\ell_2$-localization, this ratio deteriorates by at most a sublogarithmic factor for every $p, q \neq 2$. We complement our upper bounds with lower bounds that show that the electrical routing for any such $p$ and $q$ is $\Omega(\Phi^{-(1-2/p)}\log m)$-competitive. This renders our results in $\ell_1$ and $\ell_{\infty}$ unconditionally tight up to constants, and the result in any $\ell_p$- and $\ell_q$-norm to be tight in case of $\ell_2$-localization in $O(\log m)$., Comment: To appear in ICALP 2024

We present a new methodology for utilising machine learning technology in symbolic computation research. We explain how a well known human-designed heuristic to make the choice of variable ordering in cylindrical algebraic decomposition may be represented as a constrained neural network. This allows us to then use machine learning methods to further optimise the heuristic, leading to new networks of similar size, representing new heuristics of similar complexity as the original human-designed one. We present this as a form of ante-hoc explainability for use in computer algebra development., Comment: Accepted for presentation at ICMS 2024

The compact Genetic Algorithm (cGA), parameterized by its hypothetical population size $K$, offers a low-memory alternative to evolving a large offspring population of solutions. It evolves a probability distribution, biasing it towards promising samples. For the classical benchmark OneMax, the cGA has to two different modes of operation: a conservative one with small step sizes $\Theta(1/(\sqrt{n}\log n))$, which is slow but prevents genetic drift, and an aggressive one with large step sizes $\Theta(1/\log n)$, in which genetic drift leads to wrong decisions, but those are corrected efficiently. On OneMax, an easy hill-climbing problem, both modes lead to optimization times of $\Theta(n\log n)$ and are thus equally efficient. In this paper we study how both regimes change when we replace OneMax by the harder hill-climbing problem DynamicBinVal. It turns out that the aggressive mode is not affected and still yields quasi-linear runtime $O(n\cdot polylog (n))$. However, the conservative mode becomes substantially slower, yielding a runtime of $\Omega(n^2)$, since genetic drift can only be avoided with smaller step sizes of $O(1/n)$. We complement our theoretical results with simulations.

Investors and regulators can greatly benefit from a realistic market simulator that enables them to anticipate the consequences of their decisions in real markets. However, traditional rule-based market simulators often fall short in accurately capturing the dynamic behavior of market participants, particularly in response to external market impact events or changes in the behavior of other participants. In this study, we explore an agent-based simulation framework employing reinforcement learning (RL) agents. We present the implementation details of these RL agents and demonstrate that the simulated market exhibits realistic stylized facts observed in real-world markets. Furthermore, we investigate the behavior of RL agents when confronted with external market impacts, such as a flash crash. Our findings shed light on the effectiveness and adaptability of RL-based agents within the simulation, offering insights into their response to significant market events., Comment: Accpeted in IJCNN 2024

In photonic crystals the propagation of light is governed by their photonic band structure, an ensemble of propagating states grouped into bands, separated by photonic band gaps. Due to discrete symmetries in spatially strictly periodic dielectric structures their photonic band structure is intrinsically anisotropic. However, for many applications, such as manufacturing artificial structural color materials or developing photonic computing devices, but also for the fundamental understanding of light-matter interactions, it is of major interest to seek materials with long range non-periodic dielectric structures which allow the formation of {\it isotropic} photonic band gaps. Here, we report the first ever 3D isotropic photonic band gap for an optimized disordered stealthy hyperuniform structure for microwaves. The transmission spectra are directly compared to a diamond pattern and an amorphous structure with similar node density. The band structure is measured experimentally for all three microwave structures, manufactured by 3D-Laser-printing for meta-materials with refractive index up to $n=2.1$. Results agree well with finite-difference-time-domain numerical investigations and a priori calculations of the band-gap for the hyperuniform structure: the diamond structure shows gaps but being anisotropic as expected, the stealthy hyperuniform pattern shows an isotropic gap of very similar magnitude, while the amorphous structure does not show a gap at all. The centimeter scaled microwave structures may serve as prototypes for micrometer scaled structures with bandgaps in the technologically very interesting region of infrared (IR)., Comment: 9 pages, 6 figures

In this paper we are introducing a new reinforcement learning method for control problems in environments with delayed feedback. Specifically, our method employs stochastic planning, versus previous methods that used deterministic planning. This allows us to embed risk preference in the policy optimization problem. We show that this formulation can recover the optimal policy for problems with deterministic transitions. We contrast our policy with two prior methods from literature. We apply the methodology to simple tasks to understand its features. Then, we compare the performance of the methods in controlling multiple Atari games., Comment: Under Review

In this paper, we consider the problem of recovering a sum of filtered Diracs, representing an input with finite rate of innovation (FRI), from its corresponding time encoding machine (TEM) measurements. So far, the recovery was guaranteed for cases where the filter is selected from a number of particular mathematical functions. Here, we introduce a new generalized method for recovering FRI signals from the TEM output. On the theoretical front, we significantly increase the class of filters for which reconstruction is guaranteed, and provide a condition for perfect input recovery depending on the first two local derivatives of the filter. We extend this result with reconstruction guarantees in the case of noise corrupted FRI signals. On the practical front, in cases where the filter has an unknown mathematical function, the proposed method streamlines the recovery process by bypassing the filter modelling stage. We validate the proposed method via numerical simulations with filters previously used in the literature, as well as filters that are not compatible with the existing results. Additionally, we validate the results using a TEM hardware implementation.

Bandpass signals are an important sub-class of bandlimited signals that naturally arise in a number of application areas but their high-frequency content poses an acquisition challenge. Consequently, "Bandpass Sampling Theory" has been investigated and applied in the literature. In this paper, we consider the problem of modulo sampling of bandpass signals with the main goal of sampling and recovery of high dynamic range inputs. Our work is inspired by the Unlimited Sensing Framework (USF). In the USF, the modulo operation folds high dynamic range inputs into low dynamic range, modulo samples. This fundamentally avoids signal clipping. Given that the output of the modulo nonlinearity is non-bandlimited, bandpass sampling conditions never hold true. Yet, we show that bandpass signals can be recovered from a modulo representation despite the inevitable aliasing. Our main contribution includes proof of sampling theorems for recovery of bandpass signals from an undersampled representation, reaching sub-Nyquist sampling rates. On the recovery front, by considering both time-and frequency-domain perspectives, we provide a holistic view of the modulo bandpass sampling problem. On the hardware front, we include ideal, non-ideal and generalized modulo folding architectures that arise in the hardware implementation of modulo analog-to-digital converters. Numerical simulations corroborate our theoretical results. Bridging the theory-practice gap, we validate our results using hardware experiments, thus demonstrating the practical effectiveness of our methods., Comment: 24 pages, 9 figures, revised manuscript

Many optically active systems possess spatially asymmetric electron orbitals. These generate permanent dipole moments, which can be stronger than the corresponding transition dipole moments, significantly affecting the system dynamics and creating polarised Fock states of light. We derive a master equation for these systems by employing an optical polaron transformation that captures the photon mode polarisation induced by the permanent dipoles. This provides an intuitive framework to explore their influence on the system dynamics and emission spectrum. We find that permanent dipoles introduce multiple-photon processes and a photon sideband which causes substantial modifications to single-photon transition dipole processes. In the presence of an external drive, permanent dipoles lead to an additional process that we show can be exploited to optimise the decoherence and transition rates. We derive the emission spectrum of the system, highlighting experimentally detectable signatures of optical polarons, and measurements that can identify the parameters in the system Hamiltonian, the magnitude of the differences in the permanent dipoles, and the steady-state populations of the system., Comment: We have now included the dipolar self energy term in our Hamiltonian. Doing so cancelled out the internal drive of our Hamiltonian in the first version of this manuscript, and so we have now added an external drive. The net effect is that our results are mostly unchanged, but the source of the drive is different

Hyperuniform disordered photonic materials have recently been shown to display large, complete photonic band gaps and isotropic optical properties, and are emerging as strong candidates for a plethora of optoelectronic applications, making them competitive with many of their periodic and quasiperiodic counterparts. In this work, high quality factor optical cavities in hyperuniform disordered architectures are fabricated through semiconductor slabs and experimentally addressed by scanning near-field optical microscopy. The wide range of confined cavity modes that we detect arise from carefully designed local modifications of the dielectric structure. Previous works on hyperuniform disordered photonic systems have previously identified several Anderson localized states spectrally located at the PBG edges with relatively high quality factors. In this work, by engineering the structural parameters of the cavity, we achieve an experimental quality factor of order 6000 (higher than the one of the Anderson states) and we demonstrate that three types of localized modes of different nature coexist within a small area and in a relatively narrow spectral window of the disordered correlated system. Their compatibility with general boundary constraints, in contrast with ordered architectures that suffer strict layout constraints imposed by photonic crystals' axes orientation, makes optical cavities in disordered hyperuniform patterns a flexible optical insulator platform for planar optical circuits., Comment: 9 pages, 5 figures

In this article, we explore the dynamical decoherence of the chromophores within a green fluorescent protein when coupled to a finite-temperature dielectric environment. Such systems are of significant interest due to their anomalously long coherence lifetimes compared to other biomolecules. We work within the spin-boson model and employ the Hierarchical Equations of Motion formalism which allows for the accounting of the full non-perturbative and non-Markovian characteristics of the system dynamics. We analyse the level coherence of independent green fluorescent protein chromophores and the energy transfer dynamics in homo-dimer green fluorescent proteins, focusing on the effect of dielectric relaxation on the timescales of these systems. Using the Fluctuation-Dissipation theorem, we generate spectral densities from local electric susceptibility generated from Poisson's equation and employ a Debye dielectric model for the solvent environment. For different system architectures, we identify a number of very striking features in the dynamics of the chromophore induced by the dielectric relaxation of the environment, resulting in strong memory effects that extend the coherence lifetime of the system. Remarkably, the complex architecture of the green fluorescent protein, which includes a cavity-like structure around the atomic system, is well suited to preserving the coherences in the homo-dimer system. The system dynamics generate a dynamical correlation between the coherent energy transfer between its sub-systems and the entropy production, which can lead to transient reductions in entropy, a unique feature of the non-Markovian nature of the system-environment interaction.

In this article we employ a model open quantum system consisting of two-level atomic systems coupled to Lorentzian photonic cavities, as an instantiation of a quantum physical reservoir computer. We then deployed the quantum reservoir computing approach to an archetypal machine learning problem of image recognition. We contrast the effectiveness of the quantum physical reservoir computer against a conventional approach using neural network of the similar architecture with the quantum physical reservoir computer layer removed. Remarkably, as the data set size is increased the quantum physical reservoir computer quickly starts out perform the conventional neural network. Furthermore, quantum physical reservoir computer provides superior effectiveness against number of training epochs at a set data set size and outperformed the neural network approach at every epoch number sampled. Finally, we have deployed the quantum physical reservoir computer approach to explore the quantum problem associated with the dynamics of open quantum systems in which an atomic system ensemble interacts with a structured photonic reservoir associated with a photonic band gap material. Our results demonstrate that the quantum physical reservoir computer is equally effective in generating useful representations for quantum problems, even with limited training data size.

In this article we explore the dynamics of many-body atomic systems symmetrically coupled to a single Lorentzian photonic cavity. Our study reveals interesting dynamical characteristics including non-zero steady states, superradiant decay, enhanced energy transfer and the ability to modulate oscillations in the atomic system by tuning environmental degrees of freedom. We also analyse a configuration consisting of a three-atom chain embedded in a photonic cavity. Similarly, we find a strong enhancement of the energy transfer rate between the two ends of the chain and identified specific initial conditions that lead to significantly reduced dissipation between the two atoms at the end of the chain. Another configuration of interest consists of two symmetrical detuned reservoirs with respect to the atomic system. In the single-atom case, we show that it is possible to enhance the decay rate of the system by modulating its reservoir detuning, while in the many-atom case, this results in dynamics akin to the on-resonant cavity. Finally, we examine the validity of rotating wave approximation through a direct comparison against the numerically exact hierarchical equations of motion approach. We find good agreement in the weak coupling regime while in the intermediate coupling regime, we identify qualitative similarities, but the rotating wave approximation becomes less reliable. In the moderate coupling regime, we find deviation of the steady states due to the formation of mixed photon atom states.

In this paper we introduce a new sampling and reconstruction approach for multi-dimensional analog signals. Building on top of the Unlimited Sensing Framework (USF), we present a new folded sampling operator called the multi-dimensional modulo-hysteresis that is also backwards compatible with the existing one-dimensional modulo operator. Unlike previous approaches, the proposed model is specifically tailored to multi-dimensional signals. In particular, the model uses certain redundancy in dimensions 2 and above, which is exploited for input recovery with robustness. We prove that the new operator is well-defined and its outputs have a bounded dynamic range. For the noiseless case, we derive a theoretically guaranteed input reconstruction approach. When the input is corrupted by Gaussian noise, we exploit redundancy in higher dimensions to provide a bound on the error probability and show this drops to 0 for high enough sampling rates leading to new theoretical guarantees for the noisy case. Our numerical examples corroborate the theoretical results and show that the proposed approach can handle a significantly larger amount of noise compared to USF., Comment: 47 pages