Fetching the paper…
Reading the bibliography…
An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the density, for which a precise landscape of predictions has been made via statistical physics-based heuristics.
Symmetric random walks on groups
Harry Kesten · 1959
Earlier work this paper cites.
Problems and results on 3-chromatic hypergraphs and some related questions
Paul Erdős and László Lovász · 1973
Earlier work this paper cites.
Solvable model of a spin-glass
David Sherrington and Scott Kirkpatrick · 1975
Earlier work this paper cites.
New upper bounds on the rate of a code via the delsarte-macwilliams inequalities
Robert McEliece, Eugene Rodemich, Howard Rumsey, and Lloyd Welch · 1977
Earlier work this paper cites.
The complexity of satisfiability problems
Thomas J Schaefer · 1978
Earlier work this paper cites.
Infinite number of order parameters for spin-glasses
Giorgio Parisi · 1979
Earlier work this paper cites.
A sequence of approximated solutions to the SK model for spin glasses
Giorgio Parisi · 1980
Earlier work this paper cites.
The independence ratio of regular graphs
Béla Bollobás · 1981
Earlier work this paper cites.
The expected eigenvalue distribution of a large regular graph
Brendan D McKay · 1981
Earlier work this paper cites.
λ 1 \lambda_{1} , isoperimetric inequalities for graphs, and superconcentrators
Noga Alon and Vitali D Milman · 1985
Earlier work this paper cites.
Eigenvalues and expanders
Noga Alon · 1986
Earlier work this paper cites.
Explicit construction of linear sized tolerant networks
Noga Alon and Fan RK Chung · 1988
Earlier work this paper cites.
Independent sets in regular graphs and sum-free subsets of finite groups
Noga Alon · 1991
Earlier work this paper cites.
Models of random regular graphs
Nicholas C Wormald · 1999
Earlier work this paper cites.
On Markov chains for independent sets
Martin Dyer and Catherine Greenhill · 2000
Earlier work this paper cites.
Complexity of Positivstellensatz proofs for the knapsack
Dima Grigoriev · 2001
Earlier work this paper cites.
Some optimal inapproximability results
Johan Håstad · 2001
Earlier work this paper cites.
An entropy approach to the hard-core model on bipartite graphs
Jeff Kahn · 2001
Earlier work this paper cites.
A note on the Glauber dynamics for sampling independent sets
Eric Vigoda · 2001
Earlier work this paper cites.
The asymptotic order of the random k k -SAT threshold
Dimitris Achlioptas and Cristopher Moore · 2002
Earlier work this paper cites.
Relations between average case complexity and approximation complexity
Uriel Feige · 2002
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
Subhash Khot · 2002
Earlier work this paper cites.
Analytic and algorithmic solution of random satisfiability problems
Marc Mézard, Giorgio Parisi, and Riccardo Zecchina · 2002
Earlier work this paper cites.
Random k k -satisfiability problem: From an analytic solution to an efficient algorithm
Marc Mézard and Riccardo Zecchina · 2002
Earlier work this paper cites.
The threshold for random k-sat is 2 k ( ln 2 − o ( k ) ) 2^{k}(\ln 2-o(k))
Dimitris Achlioptas and Yuval Peres · 2003
Earlier work this paper cites.
Recognizing more random unsatisfiable 3-SAT instances efficiently
Andreas Goerdt and André Lanka · 2003
Earlier work this paper cites.
Classifying the complexity of constraints using finite algebras
Andrei Bulatov, Peter Jeavons, and Andrei Krokhin · 2005
Earlier work this paper cites.
Spectral techniques applied to sparse random graphs
Uriel Feige and Eran Ofek · 2005
Earlier work this paper cites.
Clustering of solutions in the random satisfiability problem
Marc Mézard, Thierry Mora, and Riccardo 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.
Threshold values of random k-sat from the cavity method
Stephan Mertens, Marc Mézard, and Riccardo Zecchina · 2006
Earlier work this paper cites.
Counting good truth assignments of random k k -SAT formulae
Andrea Montanari and Devavrat Shah · 2006
Earlier work this paper cites.
The Parisi formula
Michel Talagrand · 2006
Cited alongside, same era.
Counting independent sets up to the tree threshold
Dror Weitz · 2006
Cited alongside, same era.
On the Laplacian eigenvalues of G n , p G_{n,p}
Amin Coja-Oghlan · 2007
Cited alongside, same era.
Strong refutation heuristics for random k k -SAT
Amin Coja-Oghlan, Andreas Goerdt, and André Lanka · 2007
Cited alongside, same era.
Easily refutable subformulas of large random 3CNF formulas
Uriel Feige and Eran Ofek · 2007
Cited alongside, same era.
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007
Cited alongside, same era.
Semidefinite programs on sparse random graphs and their application to community detection
Andrea Montanari and Subhabrata Sen · 2016
Later among the works it cites.
How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
Andrej Risteski · 2016
Later among the works it cites.
Approximate maximum entropy principles via goemans-williamson with applications to provable variational methods
Andrej Risteski and Yuanzhi Li · 2016
Later among the works it cites.
Belief propagation guided decimation fails on random formulas
Amin Coja-Oghlan · 2017
Later among the works it cites.
Efficient Bayesian estimation from few samples: community detection and related problems
Samuel B Hopkins and David Steurer · 2017
Later among the works it cites.
Sum of squares lower bounds for refuting any CSP
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Florent Krzakała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová · 2007
Cited alongside, same era.
Algorithmic barriers from phase transitions
Dimitris Achlioptas and Amin Coja-Oghlan · 2008
Cited alongside, same era.
A proof of Alon’s second eigenvalue conjecture and related problems
Joel Friedman · 2008
Cited alongside, same era.
Clusters of solutions and replica symmetry breaking in random k k -satisfiability
Andrea Montanari, Federico Ricci-Tersenghi, and Guilhem Semerjian · 2008
Cited alongside, same era.
Optimal algorithms and inapproximability results for every CSP?
Prasad Raghavendra · 2008
Cited alongside, same era.
Linear level Lasserre lower bounds for certain k-CSPs
Grant Schoenebeck · 2008
Cited alongside, same era.
Pravesh K Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer · 2017
Later among the works it cites.
Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
Viresh Patel and Guus Regts · 2017
Later among the works it cites.
Strongly refuting random CSPs below the spectral threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2017
Later among the works it cites.
Lecture notes on graph partitioning, expanders, and spectral methods
Luca Trevisan · 2017
Later among the works it cites.
SOS lower bounds with hard constraints: think global, act local
Pravesh Kothari, Ryan O’Donnell, and Tselil Schramm · 2018
Later among the works it cites.
High-dimensional probability: An introduction with applications in data science
Roman Vershynin · 2018
Later among the works it cites.
Approximation via correlation decay when strong spatial mixing fails
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic · 2019
Later among the works it cites.
Statistical physics approaches to Unique Games
Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts · 2019
Later among the works it cites.
Counting solutions to random CNF formulas
Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang · 2019
Later among the works it cites.
Spectral gaps of random graphs and applications
Christopher Hoffman, Matthew Kahle, and Elliot Paquette · 2019
Later among the works it cites.
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Vishesh Jain, Frederic Koehler, and Andrej Risteski · 2019
Later among the works it cites.
A deterministic algorithm for counting colorings with 2 Δ 2\Delta colors
Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava · 2019
Later among the works it cites.
The Ising partition function: Zeros and deterministic approximation
Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava · 2019
Later among the works it cites.
Approximate counting, the Lovász local lemma, and inference in graphical models
Ankur Moitra · 2019
Later among the works it cites.
Optimization of the sherrington-kirkpatrick hamiltonian
Andrea Montanari · 2019
Later among the works it cites.
On a conjecture of Sokal concerning roots of the independence polynomial
Han Peters and Guus Regts · 2019
Later among the works it cites.
Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs
Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S Wein · 2020
Later among the works it cites.
Belief Propagation on the random k k -SAT model
Amin Coja-Oghlan, Noëla Müller, and Jean B Ravelomanana · 2020
Later among the works it cites.
Fast sampling and counting k k -SAT solutions in the local lemma regime
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang · 2020
Later among the works it cites.
Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
Weiming Feng, Kun He, and Yitong Yin · 2020
Later among the works it cites.
Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran · 2020
Later among the works it cites.
Towards the sampling Lovász Local Lemma
Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong · 2020
Later among the works it cites.
A tight degree 4 sum-of-squares lower bound for the Sherrington–Kirkpatrick Hamiltonian
Dmitriy Kunisky and Afonso S Bandeira · 2020
Later among the works it cites.
Lifting sum-of-squares lower bounds: degree-2 to degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu · 2020
Later among the works it cites.
A Proof of the CSP Dichotomy Conjecture
Dmitriy Zhuk · 2020
Later among the works it cites.
On the sampling Lovász Local Lemma for atomic constraint satisfaction problems
Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong · 2021
Closest in time.