Fetching the paper…
Reading the bibliography…
The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence.
David Sherrington and Scott Kirkpatrick, Solvable model of a spin-glass , Physical review letters 35
1975
Earlier work this paper cites.
Richard M Karp, The probabilistic analysis of some combinatorial search algorithms , Algorithms and complexity: New directions and recent results 1
1976
Earlier work this paper cites.
Michael R Garey and David S Johnson, Computers and intractability , vol. 174, freeman San Francisco, 1979
1979
Earlier work this paper cites.
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.
Narendra Karmarkar and Richard M Karp, The differencing method of set partitioning , Computer Science Division (EECS), University of California Berkeley, 1982
1982
Earlier work this paper cites.
Yaotian Fu and Philip W Anderson, Application of statistical mechanics to np-complete problems in combinatorial optimisation , Journal of Physics A: Mathematical and General 19
1986
Earlier work this paper cites.
M. Mezard, G. Parisi, and M. A. Virasoro, Spin-glass theory and beyond, vol 9 of
1987
Earlier work this paper cites.
Werner Krauth and Marc Mézard, Storage capacity of memory networks with binary couplings , Journal de Physique 50
1989
Earlier work this paper cites.
Richard Lipton, New directions in testing , Distributed Computing and Cryptography 2
1991
Earlier work this paper cites.
Mark Jerrum, Large cliques elude the metropolis process , Random Structures & Algorithms 3
1992
Earlier work this paper cites.
Scott Kirkpatrick and Bart Selman, Critical behavior in the satisfiability of random boolean expressions , Science 264
1994
Earlier work this paper cites.
Miklós Ajtai, Generating hard instances of lattice problems , Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM, 1996, pp. 99–108
1996
Earlier work this paper cites.
Jeong Han Kim and James R Roche, Covering cubes by random half cubes, with applications to binary neural networks , Journal of Computer and System Sciences 56
1998
Earlier work this paper cites.
E. Friedgut, Sharp thresholds of graph proprties, and the k k -SAT problem , J. Amer. Math. Soc. 4
1999
Earlier work this paper cites.
J. Hastad, Clique is hard to approximate within n 1 − ϵ n^{1-\epsilon} , Acta Math. 182
1999
Earlier work this paper cites.
Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, and Lidror Troyansky, Determining computational complexity from characteristic ?phase transitions? , Nature 400
1999
Earlier work this paper cites.
Carla P Gomes and Bart Selman, Satisfied with physics , Science 297
2002
Earlier work this paper cites.
Marc Mézard, Giorgio Parisi, and Riccardo Zecchina, Analytic and algorithmic solution of random satisfiability problems , Science 297
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.
M. Mézard, T. Mora, and R. Zecchina, Clustering of solutions in the random satisfiability problem , Physical Review Letters 94
2005
Earlier work this paper cites.
Dimitris Achlioptas and Federico Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems , Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, 2006, pp. 130–139
2006
Earlier work this paper cites.
Alfredo Braunstein and Riccardo Zecchina, Learning by message passing in networks of discrete synapses , Physical review letters 96
2006
Earlier work this paper cites.
F. Krzakała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová, Gibbs states and the set of solutions of random constraint satisfaction problems , Proceedings of the National Academy of Sciences 104
2007
Earlier work this paper cites.
Stefan Boettcher and Stephan Mertens, Analysis of the karmarkar-karp differencing algorithm , The European Physical Journal B 65
2008
Earlier work this paper cites.
2009
Earlier work this paper cites.
M. Mezard and A. Montanari, Information, physics and computation , Oxford graduate texts, 2009
2009
Cited alongside, same era.
Federico Ricci-Tersenghi and Guilhem Semerjian, On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms , Journal of Statistical Mechanics: Theory and Experiment 2009
2009
Cited alongside, same era.
Amin Coja-Oghlan, A better algorithm for random k-sat , SIAM Journal on Computing 39
2010
Cited alongside, same era.
Federico Ricci-Tersenghi, Being glassy without being hard to solve , Science 330
2010
Cited alongside, same era.
M. Talagrand, Mean field models for spin glasses: Volume I: Basic examples , Springer, 2010
2010
Cited alongside, same era.
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.
Louise Budzynski, Federico Ricci-Tersenghi, and Guilhem Semerjian, Biased landscapes for random constraint satisfaction problems , Journal of Statistical Mechanics: Theory and Experiment 2019
2019
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.
Jian Ding and Nike Sun, Capacity lower bound for the ising perceptron , Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, pp. 816–827
2019
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 , Ann. Appl. Probab. To appear (2019)
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Peter Bühlmann and Sara Van De Geer, Statistics for high-dimensional data: methods, theory and applications , Springer Science & Business Media, 2011
2011
Cited alongside, same era.
A. Coja-Oghlan, On belief propagation guided decimation for random k-SAT , Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2011, pp. 957–966
2011
Cited alongside, same era.
Simon Foucart and Holger Rauhut, A mathematical introduction to compressive sensing , Springer, 2013
2013
Cited alongside, same era.
Dmitry Panchenko, The sherrington-kirkpatrick model , Springer Science & Business Media, 2013
2013
Cited alongside, same era.
2014
Cited alongside, same era.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun, The loss surfaces of multilayer networks , Artificial intelligence and statistics, 2015, pp. 192–204
2015
Cited alongside, same era.
Jian Ding, Allan Sly, and Nike Sun, Proof of the satisfiability conjecture for large k , Proceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 59–68
2015
Cited alongside, same era.
2019
Later among the works it cites.
2019
Later among the works it cites.
2019
Later among the works it cites.
2019
Later among the works it cites.
Andrea Montanari, Optimization of the sherrington-kirkpatrick hamiltonian , 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2019, pp. 1417–1433
2019
Later among the works it cites.
2020
Later among the works it cites.
Gérard Ben Arous, Alexander S Wein, and Ilias Zadik, Free energy wells and overlap gap property in sparse pca , Conference on Learning Theory, PMLR, 2020, pp. 479–482
2020
Later among the works it cites.
Carlo Baldassi, Riccardo Della Vecchia, Carlo Lucibello, and Riccardo Zecchina, Clustering of solutions in the symmetric binary perceptron , Journal of Statistical Mechanics: Theory and Experiment 2020
2020
Later among the works it cites.
Louise Budzynski and Guilhem Semerjian, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion , Journal of Statistical Mechanics: Theory and Experiment 2020
2020
Later among the works it cites.
Ronen Eldan, A simple approach to chaos for p-spin models , Journal of Statistical Physics 181
2020
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
2020
Later among the works it cites.
2020
Later among the works it cites.
2020
Later among the works it cites.
Paxton Turner, Raghu Meka, and Philippe Rigollet, Balancing gaussian vectors in high dimension , Conference on Learning Theory, PMLR, 2020, pp. 3455–3486
2020
Later among the works it cites.
2020
Later among the works it cites.
2021
Closest in time.
Gérard Ben Arous and Aukosh Jagannath, Shattering versus metastability in spin glasses , arXiv e-prints (2021), arXiv–2104
2021
Closest in time.
2021
Closest in time.
2021
Closest in time.
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
Closest in time.