Fetching the paper…
Reading the bibliography…
We consider the problem of finding a near ground state of a $p$-spin model with Rademacher couplings by means of a low-depth circuit.
Giorgio Parisi, A sequence of approximated solutions to the SK model for spin glasses , Journal of Physics A: Mathematical and General 13
1980
Earlier work this paper cites.
Johan Håstad, Almost optimal lower bounds for small depth circuits , Proceedings of the eighteenth annual ACM symposium on Theory of computing, 1986, pp. 6–20
1986
Earlier work this paper cites.
Merrick L Furst, Jeffrey C Jackson, and Sean W Smith, Improved learning of AC0 functions , COLT, vol. 91, 1991, pp. 317–325
1991
Earlier work this paper cites.
Nathan Linial, Yishay Mansour, and Noam Nisan, Constant depth circuits, fourier transform, and learnability , Journal of the ACM (JACM) 40
1993
Earlier work this paper cites.
M. Sipser, Introduction to the theory of computability , PWS Publishing Company, 1997
1997
Earlier work this paper cites.
F. Guerra and F. L. Toninelli, The thermodynamic limit in mean field spin glass models , Commun. Math. Phys. 230
2002
Earlier work this paper cites.
Noga Alon and Joel H Spencer, The probabilistic method , John Wiley & Sons, 2004
2004
Earlier work this paper cites.
Philippe Carmona and Yueyun Hu, Universality in Sherrington–Kirkpatrick’s spin glass model , Annales de l’Institut Henri Poincare (B) Probability and Statistics, vol. 42, Elsevier, 2006, pp. 215–222
2006
Earlier work this paper cites.
Michel Talagrand, The Parisi formula , Annals of mathematics (2006), 221–263
2006
Cited alongside, same era.
Sanjeev Arora and Boaz Barak, Computational complexity: a modern approach , Cambridge University Press, 2009
2009
Cited alongside, same era.
Benjamin Rossman, Average-case complexity of detecting cliques , Ph.D. thesis, Massachusetts Institute of Technology, 2010
2010
Cited alongside, same era.
Dmitry Panchenko, The Sherrington-Kirkpatrick model , Springer Science & Business Media, 2013
2013
Cited alongside, same era.
Ryan O’Donnell, Analysis of boolean functions , Cambridge University Press, 2014
2014
Cited alongside, same era.
Antonio Auffinger and Wei-Kuo Chen, Universality of chaos and ultrametricity in mixed p-spin models , Communications on Pure and Applied Mathematics 69
Subhabrata Sen, Optimization on sparse random hypergraphs and spin glasses , Random Structures & Algorithms 53
2018
Later among the works it cites.
Roman Vershynin, High-dimensional probability: An introduction with applications in data science , vol. 47, Cambridge University Press, 2018
2018
Later among the works it cites.
Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman, Suboptimality of local algorithms for a class of max-cut problems , The Annals of Probability 47
2019
Later among the works it cites.
2020
Later among the works it cites.
David Gamarnik, Aukosh Jagannath, and Alexander S Wein, Low-degree hardness of random optimization problems , 61st Annual Symposium on Foundations of Computer Science, 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2016
Cited alongside, same era.
Yuan Li, Alexander Razborov, and Benjamin Rossman, On the AC0 complexity of subgraph isomorphism , SIAM Journal on Computing 46
2017
Cited alongside, same era.
Avishay Tal, Tight bounds on the fourier spectrum of AC0 , 32nd Computational Complexity Conference (CCC 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017
2017
Cited alongside, same era.
2020
Later among the works it cites.
David Gamarnik and Aukosh Jagannath, The overlap gap property and approximate message passing algorithms for p p -spin models , The Annals of Probability 49
2021
Closest in time.
Andrea Montanari, Optimization of the Sherrington–Kirkpatrick hamiltonian , SIAM Journal on Computing (2021), FOCS19–1
2021
Closest in time.
Eliran Subag, Following the ground states of full-RSB spherical spin glasses , Communications on Pure and Applied Mathematics 74
2021
Closest in time.