More Like this

1. Slope gap distribution of saddle connections on the 2n-gon

   https://doi.org/10.3934/dcds.2022141  

   Berman, Jonah; McAdam, Taylor; Miller-Murthy, Ananth; Uyanik, Caglar; Wan, Hamilton (January 2023, Discrete and Continuous Dynamical Systems)

   We explicitly compute the limiting slope gap distribution for saddle connections on any 2n-gon for n greater than or equal to 3. Our calculations show that the slope gap distribution for a translation surface is not always unimodal, answering a question of Athreya. We also give linear lower and upper bounds for number of non-differentiability points as n grows. The latter result exhibits the first example of a non-trivial bound on an infinite family of translation surfaces and answers a question by Kumanduri-Sanchez-Wang. 

   more » « less
2. Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent

   Goel, Surbhi; Gollakota, Aravind; Jin, Zhihan; Karmalkar, Sushrut; Klivans, Adam (July 2020, International Conference on Machine Learning)

   We prove the first superpolynomial lower bounds for learning one-layer neural networks with respect to the Gaussian distribution using gradient descent. We show that any classifier trained using gradient descent with respect to square-loss will fail to achieve small test error in polynomial time given access to samples labeled by a one-layer neural network. For classification, we give a stronger result, namely that any statistical query (SQ) algorithm (including gradient descent) will fail to achieve small test error in polynomial time. Prior work held only for gradient descent run with small batch sizes, required sharp activations, and applied to specific classes of queries. Our lower bounds hold for broad classes of activations including ReLU and sigmoid. The core of our result relies on a novel construction of a simple family of neural networks that are exactly orthogonal with respect to all spherically symmetric distributions. 

   more » « less
3. Gardner formula for Ising perceptron models at small densities

   Bolthausen, E.; Nakajima, S; Sun, N; Xu, C (January 2022, Conference on Learning Theory)

   We consider the Ising perceptron model with N spins and M = N*alpha patterns, with a general activation function U that is bounded above. For U bounded away from zero, or U a one-sided threshold function, it was shown by Talagrand (2000, 2011) that for small densities alpha, the free energy of the model converges in the large-N limit to the replica symmetric formula conjectured in the physics literature (Krauth–Mezard 1989, see also Gardner–Derrida 1988). We give a new proof of this result, which covers the more general class of all functions U that are bounded above and satisfy a certain variance bound. The proof uses the (first and second) moment method conditional on the approximate message passing iterates of the model. In order to deduce our main theorem, we also prove a new concentration result for the perceptron model in the case where U is not bounded away from zero. 

   more » « less
4. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

   https://doi.org/10.1145/3313276.3316404  

   Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay (June 2019, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing)

   Recently, Bravyi, Gosset, and Konig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem. 

   more » « less
5. Linear Sketching over F_2

   https://doi.org/10.4230/LIPIcs.CCC.2018.8  

   Kannan, Sampath; Mossel, Elchanan; Sanyal, Swagato; Yaroslavtsev, Grigory (August 2018, Leibniz international proceedings in informatics)

   We initiate a systematic study of linear sketching over F_2. For a given Boolean function treated as f : F_2^n -> F_2 a randomized F_2-sketch is a distribution M over d x n matrices with elements over F_2 such that Mx suffices for computing f(x) with high probability. Such sketches for d << n can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between F_2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F_2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F_2-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F_2-sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F_2 can be constructed as F_2-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does not require the stream length to be triply exponential in n and holds for streams of length O(n) constructed through uniformly random updates. 

   more » « less