Fetching the paper…
Reading the bibliography…
We show that two related classes of algorithms, stable algorithms and Boolean circuits with bounded depth, cannot produce an approximate sample from the uniform measure over the set of solutions to the symmetric binary perceptron model at any constraint-to-variable density.
Carl-Gustav Esseen, On mean central limit theorems , Kungl. Tekn. Högsk. Handl. Stockholm (1958)
1958
Earlier work this paper cites.
Aad W Van der Vaart, Asymptotic statistics , vol. 3, Cambridge university press, 1998
1998
Earlier work this paper cites.
Fedor Nazarov, On the maximal perimeter of a convex set in r ˆ n with respect to a gaussian measure , Geometric Aspects of Functional Analysis: Israel Seminar 2001-2002, Springer, 2003, pp. 169–187
2003
Earlier work this paper cites.
Emmanuel Rio, Upper bounds for minimal distances in the central limit theorem , Annales de l’IHP Probabilités et statistiques, vol. 45, 2009, pp. 802–817
2009
Earlier work this paper cites.
Larry Goldstein, Bounds on the constant in the mean central limit theorem , The Annals of Probability 38
2010
Earlier work this paper cites.
D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi, On the solution space geometry of random formulas , Random Structures and Algorithms 38
2011
Earlier work this paper cites.
Ryan O’Donnell, Analysis of boolean functions , Cambridge University Press, 2014
2014
Earlier work this paper cites.
2017
Earlier work this paper cites.
Richard M Dudley, Real analysis and probability , Chapman and Hall/CRC, 2018
2018
Earlier work this paper cites.
Roman Vershynin, High-dimensional probability: An introduction with applications in data science , vol. 47, Cambridge university press, 2018
2018
Cited alongside, same era.
A Zhai, A multivariate clt in wasserstein distance with near optimal convergence rate , Probab. Theory Related Fields 170
2018
Cited alongside, same era.
Benjamin Aubin, Will Perkins, and Lenka Zdeborova, Storage capacity in symmetric binary perceptrons , Journal of Physics A: Mathematical and Theoretical 52
2019
Cited alongside, same era.
Yang Song and Stefano Ermon, Generative modeling by estimating gradients of the data distribution , Advances in neural information processing systems 32
2019
Cited alongside, same era.
Nikhil Bansal and Joel H Spencer, On-line balancing of random inputs , Random Structures & Algorithms 57
2020
Cited alongside, same era.
Emmanuel Abbe, Shuangning Li, and Allan Sly, Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron , 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2022, pp. 327–338
2022
Later among the works it cites.
Emmanuel Abbe, Shuangping Li, and Allan Sly, Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster , Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 860–873
2022
Later among the works it cites.
2022
Later among the works it cites.
2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
David Gamarnik, Aukosh Jagannath, and Alexander S. Wein, Low-degree hardness of random optimization problems , Proceedings of 61st FOCS, IEEE, 2020, pp. 131–140
2020
Cited alongside, same era.
David Gamarnik, The overlap gap property: A topological barrier to optimizing over random structures , Proceedings of the National Academy of Sciences 118
2021
Cited alongside, same era.
Will Perkins and Changji Xu, Frozen 1-rsb structure of the symmetric ising perceptron , Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 1579–1588
2021
Cited alongside, same era.
2022
Later among the works it cites.
2023
Later among the works it cites.
2023
Later among the works it cites.