Fetching the paper…
Reading the bibliography…
For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs.
Statistical theory of superlattices
H. A. Bethe · 1935
Earlier work this paper cites.
Infinite number of order parameters for spin-glasses
G. Parisi · 1979
Earlier work this paper cites.
Random-energy model: An exactly solvable model of disordered systems
B. Derrida · 1981
Earlier work this paper cites.
A generalization of the random energy model which includes correlations between energies
B. Derrida · 1985
Earlier work this paper cites.
Spin glasses with p \smash{p} -spin interactions
E. Gardner · 1985
Earlier work this paper cites.
A mathematical reformulation of Derrida’s REM and GREM
D. Ruelle · 1987
Earlier work this paper cites.
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
D. Grigoriev · 2001
Earlier work this paper cites.
The k \smash{k} -SAT problem in a simple limit
L. Leuzzi and G. Parisi · 2001
Earlier work this paper cites.
The Bethe lattice spin glass revisited
M. Mézard and G. Parisi · 2001
Earlier work this paper cites.
Bethe free energy, Kikuchi approximations, and belief propagation algorithms
J. S. Yedidia, W. T. Freeman, and Y. Weiss · 2001
Earlier work this paper cites.
The asymptotic order of the random k \smash{k} -SAT threshold
D. Achlioptas and C. Moore · 2002
Earlier work this paper cites.
The 3 \smash{3} -SAT problem with large number of clauses in the ∞ \smash{\infty} -replica symmetry breaking scheme
A. Crisanti, L. Leuzzi, and G. Parisi · 2002
Earlier work this paper cites.
Relations between average case complexity and approximation complexity
U. Feige · 2002
Earlier work this paper cites.
The thermodynamic limit in mean field spin glass models
F. Guerra and F. L. Toninelli · 2002
Earlier work this paper cites.
Extended variational principle for the Sherrington–Kirkpatrick spin-glass model
M. Aizenman, R. Sims, and S. L. Starr · 2003
Earlier work this paper cites.
Broken replica symmetry bounds in the mean field spin glass model
F. Guerra · 2003
Earlier work this paper cites.
On the nature of the low-temperature phase in discontinuous mean-field spin glasses
A. Montanari and F. Ricci-Tersenghi · 2003
Earlier work this paper cites.
Derrida’s generalised random energy models. I. Models with finitely many hierarchies
A. Bovier and I. Kurkova · 2004
Cited alongside, same era.
Derrida’s generalized random energy models. II. Models with continuous hierarchies
A. Bovier and I. Kurkova · 2004
Cited alongside, same era.
Threshold values, stability analysis, and high- q \smash{q} asymptotics for the coloring problem on random graphs
F. Krzakala, A. Pagnani, and M. Weigt · 2004
Cited alongside, same era.
Bounds for diluted mean-fields spin glass models
D. Panchenko and M. Talagrand · 2004
Cited alongside, same era.
On the solution-space geometry of random constraint satisfaction problems
D. Achlioptas and F. Ricci-Tersenghi · 2006
Cited alongside, same era.
On the maximum satisfiability of random formulas
D. Achlioptas, A. Naor, and Y. Peres · 2007
Right-convergence of sparse random graphs
D. Gamarnik · 2014
Later among the works it cites.
How to refute a random CSP
S. R. Allen, R. O’Donnell, and D. Witmer · 2015
Later among the works it cites.
Satisfiability threshold for random regular NAE-SAT
J. Ding, A. Sly, and N. Sun · 2016
Later among the works it cites.
The number of solutions for random regular NAE-SAT
A. Sly, N. Sun, and Y. Zhang · 2016
Later among the works it cites.
Parisi formula for the ground state energy in the mixed p \smash{p} -spin model
A. Auffinger and W.-K. Chen · 2017
Later among the works it cites.
The SK model is full-step replica symmetry breaking at zero temperature
A. Auffinger, W.-K. Chen, and Q. Zeng · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Strong refutation heuristics for random k \smash{k} -SAT
A. Coja-Oghlan, A. Goerdt, and A. Lanka · 2007
Cited alongside, same era.
Gibbs states and the set of solutions of random constraint satisfaction problems
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová · 2007
Cited alongside, same era.
Algorithmic barriers from phase transitions
D. Achlioptas and A. Coja-Oghlan · 2008
Cited alongside, same era.
Linear level Lasserre lower bounds for certain k \smash{k} -CSPs
G. Schoenebeck · 2008
Cited alongside, same era.
Information, physics, and computation
M. Mézard and A. Montanari · 2009
Cited alongside, same era.
Reconstruction and clustering in random constraint satisfaction problems
A. Montanari, R. Restrepo, and P. Tetali · 2011
Cited alongside, same era.
Extremal cuts of sparse random graphs
A. Dembo, A. Montanari, and S. Sen · 2017
Later among the works it cites.
Sum of squares lower bounds for refuting any CSP
P. K. Kothari, R. Mori, R. O’Donnell, and D. Witmer · 2017
Later among the works it cites.
Strongly refuting random CSPs below the spectral threshold
P. Raghavendra, S. Rao, and T. Schramm · 2017
Later among the works it cites.
The algorithmic hardness threshold for continuous random energy models
L. Addario-Berry and P. Maillard · 2018
Later among the works it cites.
Charting the replica symmetric phase
A. Coja-Oghlan, C. Efthymiou, N. Jaafari, M. Kang, and T. Kapetanopoulos · 2018
Later among the works it cites.
Information-theoretic thresholds from the cavity method
A. Coja-Oghlan, F. Krzakala, W. Perkins, and L. Zdeborová · 2018
Later among the works it cites.
Optimization of the Sherrington–Kirkpatrick Hamiltonian
A. Montanari · 2018
Later among the works it cites.
On the k \smash{k} -SAT model with large number of clauses
D. Panchenko · 2018
Later among the works it cites.
Optimization on sparse random hypergraphs and spin glasses
S. Sen · 2018
Later among the works it cites.
Following the ground-states of full-RSB spherical spin glasses
E. Subag · 2018
Later among the works it cites.