Fetching the paper…
Reading the bibliography…
We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions.
The probabilistic analysis of some combinatorial search algorithms
Richard M Karp · 1976
Earlier work this paper cites.
Replica Symmetry-Breaking and the Nature of the Spin-Glass Phase
Marc Mézard, Giorgio Parisi, Nicolas Sourlas, Gérard Toulouse, and Miguel Virasoro · 1984
Earlier work this paper cites.
Almost optimal lower bounds for small depth circuits
Johan Hastad · 1986
Earlier work this paper cites.
On the independence number of random graphs
Alan Frieze · 1990
Earlier work this paper cites.
Improved learning of AC0 functions
Merrick L Furst, Jeffrey C Jackson, and Sean W Smith · 1991
Earlier work this paper cites.
Probability in Banach spaces
Michel Ledoux and Michel Talagrand · 1991
Earlier work this paper cites.
The spherical p-spin interaction spin-glass model
A Crisanti, H Horner, and H-J Sommers · 1993
Earlier work this paper cites.
Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model
Leticia F. Cugliandolo and Jorge Kurchan · 1993
Earlier work this paper cites.
Constant depth circuits, fourier transform, and learnability
Nathan Linial, Yishay Mansour, and Noam Nisan · 1993
Earlier work this paper cites.
Gaussian hilbert spaces
Svante Janson · 1997
Earlier work this paper cites.
Introduction to the Theory of Computability
M. Sipser · 1997
Earlier work this paper cites.
Out of equilibrium dynamics in spin-glasses and other glassy systems
Jean-Philippe Bouchaud, Leticia F Cugliandolo, Jorge Kurchan, and Marc Mézard · 1998
Earlier work this paper cites.
Aging of spherical spin glasses
Gérard Ben Arous, Amir Dembo, and Alice Guionnet · 2001
Earlier work this paper cites.
Aging and spin-glass dynamics
Gérard Ben Arous · 2002
Earlier work this paper cites.
The thermodynamic limit in mean field spin glass models
Francesco Guerra and Fabio Lucio Toninelli · 2002
Earlier work this paper cites.
Stochastic analysis on manifolds
Elton P. Hsu · 2002
Earlier work this paper cites.
Course 7: Dynamics of glassy systems
Leticia F Cugliandolo · 2003
Earlier work this paper cites.
The probabilistic method
Noga Alon and Joel H Spencer · 2004
Earlier work this paper cites.
Clustering of solutions in the random satisfiability problem
M. Mézard, T. Mora, and R. Zecchina · 2005
Earlier work this paper cites.
On the solution-space geometry of random constraint satisfaction problems
Dimitris Achlioptas and Federico Ricci-Tersenghi · 2006
Earlier work this paper cites.
Cugliandolo-Kurchan equations for dynamics of spin-glasses
Gérard Ben Arous, Amir Dembo, and Alice Guionnet · 2006
Earlier work this paper cites.
Dynamics for spherical models of spin-glass and aging
Alice Guionnet · 2007
Earlier work this paper cites.
Large independent sets in regular graphs of large girth
J. Lauer and N.C. Wormald · 2007
Earlier work this paper cites.
Computational complexity: a modern approach
Sanjeev Arora and Boaz Barak · 2009
Earlier work this paper cites.
Message-passing algorithms for compressed sensing
David L Donoho, Arian Maleki, and Andrea Montanari · 2009
Earlier work this paper cites.
Average-case complexity of detecting cliques
Benjamin Rossman · 2010
Earlier work this paper cites.
On independent sets in random graphs
A. Coja-Oghlan and C. Efthymiou · 2011
Cited alongside, same era.
Ordinary differential equations and dynamical systems
Gerald Teschl · 2012
Cited alongside, same era.
Random matrices and complexity of spin glasses
Antonio Auffinger, Gérard Ben Arous, and Jiří Černý · 2013
Cited alongside, same era.
Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
Mohsen Bayati, David Gamarnik, and Prasad Tetali · 2013
Cited alongside, same era.
The Sherrington-Kirkpatrick model
Dmitry Panchenko · 2013
Cited alongside, same era.
Analysis of boolean functions
Ryan O’Donnell · 2014
Cited alongside, same era.
A statistical model for tensor PCA
High-dimensional probability: An introduction with applications in data science
Roman Vershynin · 2018
Later among the works it cites.
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin · 2019
Later among the works it cites.
Computational hardness of certifying bounds on constrained PCA problems
Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein · 2019
Later among the works it cites.
Suboptimality of local algorithms for a class of max-cut problems
Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman · 2019
Later among the works it cites.
Subexponential-time algorithms for sparse PCA
Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Emile Richard and Andrea Montanari · 2014
Cited alongside, same era.
Tensor principal component analysis via sum-of-square proofs
Samuel B Hopkins, Jonathan Shi, and David Steurer · 2015
Cited alongside, same era.
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer · 2016
Cited alongside, same era.
Large deviations
S. R. S. Varadhan · 2016
Cited alongside, same era.
Walksat stalls well below satisfiability
Amin Coja-Oghlan, Amir Haqshenas, and Samuel Hetterich · 2017
Cited alongside, same era.
Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed p-spin models
Wei-Kuo Chen and Arnab Sen · 2017
Cited alongside, same era.
On the spectral gap of spherical spin glass dynamics
Reza Gheissari and Aukosh Jagannath · 2019
Later among the works it cites.
Dynamics of mean field spin glasses on short and long timescales
Aukosh Jagannath · 2019
Later among the works it cites.
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Later among the works it cites.
Optimization of the Sherrington-Kirkpatrick hamiltonian
Andrea Montanari · 2019
Later among the works it cites.
The Kikuchi hierarchy and tensor PCA
Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore · 2019
Later among the works it cites.
How to iron out rough landscapes and get optimal performances: Averaged gradient descent and its application to tensor PCA
Giulio Biroli, Chiara Cammarota, and Federico Ricci-Tersenghi · 2020
Closest in time.
Algorithmic thresholds for tensor pca
Gérard Ben Arous, Reza Gheissari, and Aukosh Jagannath · 2020
Closest in time.
Bounding flows for spherical spin glass dynamics
Gérard Ben Arous, Reza Gheissari, and Aukosh Jagannath · 2020
Closest in time.
Low-degree hardness of random optimization problems
David Gamarnik, Aukosh Jagannath, and Alexander S Wein · 2020
Closest in time.
Classical and quantum algorithms for tensor principal component analysis
Matthew B Hastings · 2020
Closest in time.
On the unbalanced cut problem and the generalized sherrington–kirkpatrick model
Aukosh Jagannath and Subhabrata Sen · 2020
Closest in time.
The algorithmic phase transition of random k-SAT for low degree polynomials
Guy Bresler and Brice Huang · 2021
Closest in time.
Optimization of mean-field spin glasses
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2021
Closest in time.
The overlap gap property: A topological barrier to optimizing over random structures
David Gamarnik · 2021
Closest in time.
The overlap gap property and approximate message passing algorithms for p p -spin models
David Gamarnik and Aukosh Jagannath · 2021
Closest in time.
Circuit lower bounds for the p-spin optimization problem
David Gamarnik, Aukosh Jagannath, and Alexander S Wein · 2021
Closest in time.
Tight lipschitz hardness for optimizing mean field spin glasses
Brice Huang and Mark Sellke · 2021
Closest in time.
Optimizing mean field spin glasses with external field
Mark Sellke · 2021
Closest in time.
Following the ground states of full-rsb spherical spin glasses
Eliran Subag · 2021
Closest in time.
Optimal low-degree hardness of maximum independent set
Alexander S Wein · 2022
Closest in time.