Search

We present a new proof (based on spectral decomposition) of a bound originally proved by Sidelnikov~\, for the frame potentials $\sum_{ij} \left( {\bf P}_i \cdot {\bf P}_j \right)^\ell $ on a unit--sphere in $d$ dimensions. Sidelnikov's bound is a special case of the lower bound for the weighted sums $\sum_{ij} f_i f_j \left( {\bf P}_i \cdot {\bf P}_j \right)^\ell$, where $f_i>0$ are scalar quantities associated to each point on the sphere, which we also prove using spectral decomposition. Moreover, in three dimensions, again using spectral decomposition, we find a sharp upper bound for $\sum_{ijk}^N \left[ \left( {\bf P}_i \times {\bf P}_j\right) \cdot {\bf P}_k \right]^2$. We explore two applications of these bounds: first, we examine configurations of points corresponding to the local minima of the Thomson problem for $N=972$; second, we analyze various distributions of points within a three-dimensional volume, where a suitable weighted sum is defined to satisfy a specific bound., Comment: 22 pages, 6 figures

We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree $\Delta$, any classical (deterministic or randomized) LOCAL model algorithm will require $\Omega(\Delta)$ rounds to solve the iterated GHZ problem, while the problem can be solved in $1$ round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires $\Omega(\Delta)$ rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner., Comment: 64 pages, 9 figures

According to the Hughes phenomenon, the major challenges encountered in computations with learning models comes from the scale of complexity, e.g. the so-called curse of dimensionality. There are various approaches for accelerate learning computations with minimal loss of accuracy. These approaches range from model-level to implementation-level approaches. To the best of our knowledge, the first one is rarely used in its basic form. Perhaps, this is due to theoretical understanding of mathematical insights of model decomposition approaches, and thus the ability of developing mathematical improvements has lagged behind. We describe a model-level decomposition approach that combines both the decomposition of the operators and the decomposition of the network. We perform a feasibility analysis on the resulting algorithm, both in terms of its accuracy and scalability.

In this short note we resort to the well known Hellmann-Feynman theorem to prove that some non-relativistic Hamiltonian operators support an infinite number of bound states.

We consider a truncation of the BMN matrix model to a configuration of two fuzzy spheres, described by two coupled non-linear oscillators dependent on the mass parameter $\mu$. The classical phase diagram of the system generically ($\mu \neq 0$) contains three equilibrium points: two centers and a center-saddle; as $\mu \to 0$ the system exhibits a pitchfork bifurcation. We demonstrate that the system is exactly integrable in quadratures for $\mu=0$, while for very large values of $\mu$, it approaches another integrable point characterized by two harmonic oscillators. The classical phase space is mixed, containing both integrable islands and chaotic regions, as evidenced by the classical Lyapunov spectrum. At the quantum level, we explore indicators of early and late time chaos. The eigenvalue spacing is best described by a Brody distribution, which interpolates between Poisson and Wigner distributions; it dovetails, at the quantum level, the classical results and reemphasizes the notion that the quantum system is mixed. We also study the spectral form factor and the quantum Lyapunov exponent, as defined by out-of-time-ordered correlators. These two indicators of quantum chaos exhibit weak correlations with the Brody distribution. We speculate that the behavior of the system as $\mu \to 0$ dominates the spectral form factor and the quantum Lyapunov exponent, making these indicators of quantum chaos less effective in the context of a mixed phase space., Comment: 34 pages, 3 tables, 21 figures. V2: References added

We have studied the packing of congruent disks on a spherical cap, for caps of different size and number of disks, $N$. This problem has been considered before only in the limit cases of circle packing inside a circle and on a sphere (Tammes problem), whereas all intermediate cases are unexplored. Finding the preferred packing configurations for a domain with both curvature and border could be useful in the description of physical and biological systems (for example, colloidal suspensions or the compound eye of an insect), with potential applications in engineering and architecture (e.g. geodesic domes). We have carried out an extensive search for the densest packing configurations of congruent disks on spherical caps of selected angular widths ($\theta_{\rm max} = \pi/6$, $\pi/4$, $\pi/2$, $3\pi/4$, $5 \pi/6$) and for several values of $N$. The numerical results obtained in the present work have been used to establish (at least qualitatively) some general features for these configurations, in particular the behavior of the packing fraction as function of the number of disks and of the angular width of the cap, or the nature of the topological defects in these configurations (it found that as the curvature increases the overall topological on the border tends to become more negative). Finally we have studied the packing configurations for $N = 19$, $37$, $61$, $91$ (hexagonal numbers) for caps ranging from the flat disk to the whole sphere, to observe the evolution (and eventual disappearance) of the curved hexagonal packing configurations while increasing the curvature., Comment: 34 pages, 21 figures; added a reference; final version accepted on Physics of Fluids

We test the analytical expressions for the first two eigenvalues of the harmonic oscillator with a Gaussian perturbation proposed recently. Our numerical eigenvalues show that those expressions are valid in an interval of the coupling parameter that is greater than the one estimated by the authors. We also calculate critical values of the coupling parameter and several exceptional points in the complex plane.

We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: 1. All LCL problems solvable with locality $O(\log^\star n)$ in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality $O(1)$. This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. 2. In rooted trees, if we can solve an LCL problem with locality $o(\log \log \log n)$ in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality $O(\log^\star n)$ in the classical deterministic LOCAL model. One of many implications is that in rooted trees, $O(\log^\star n)$ locality in quantum-LOCAL is not stronger than $O(\log^\star n)$ locality in classical LOCAL., Comment: 67 pages, 10 figures. This version corrects a mistake in v1 and in v2

The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialised neural networks likely contain subnetworks that perform well without any training. Although unstructured pruning has been extensively studied in this context, its structured counterpart, which can deliver significant computational and memory efficiency gains, has been largely unexplored. One of the main reasons for this gap is the limitations of the underlying mathematical tools used in formal analyses of the SLTH. In this paper, we overcome these limitations: we leverage recent advances in the multidimensional generalisation of the Random Subset-Sum Problem and obtain a variant that admits the stochastic dependencies that arise when addressing structured pruning in the SLTH. We apply this result to prove, for a wide class of random Convolutional Neural Networks, the existence of structured subnetworks that can approximate any sufficiently smaller network. This result provides the first sub-exponential bound around the SLTH for structured pruning, opening up new avenues for further research on the hypothesis and contributing to the understanding of the role of over-parameterization in deep learning., Comment: To be published in the 37th Conference on Neural Information Processing Systems (NeurIPS 2023)