The asymptotic $k$-SAT threshold

Abstract

Since the early 2000s physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures on phase transitions in random problems [Mezard, Parisi, Zecchina: Science 2002]. The cavity method predicts that the satisfiability threshold in the random $k$-SAT problem is $2^k\ln 2-\frac{1}{2}(1+\ln 2)+{\epsilon }_k$, with ${\lim }_{k\to \infty }{\epsilon }_k=0$ [Mertens, Mezard, Zecchina: Random Structures and Algorithms 2006]. This paper contains a proof of that conjecture.

References in corpus (5)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Survey propagation: an algorithm for satisfiability
• Maximum independent sets on random regular graphs
• On the chromatic number of random regular graphs
• Bounds on Threshold of Regular Random $k$-SAT

Cited by in corpus (20)

• Information-theoretic thresholds from the cavity method
• Minimal contagious sets in random regular graphs
• Information-theoretic and algorithmic thresholds for group testing
• Walksat stalls well below the satisfiability threshold
• Harnessing the Bethe free energy
• The large deviations of the whitening process in random constraint satisfaction problems
• Spin systems on Bethe lattices
• The random 2-SAT partition function
• The replica symmetric phase of random constraint satisfaction problems
• Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT
• Circular Coloring of Random Graphs: Statistical Physics Investigation
• Streamlining Variational Inference for Constraint Satisfaction Problems
• On the Max-Cut of Sparse Random Graphs
• The Satisfiability Threshold for Non-Uniform Random 2-SAT
• The number of solutions for random regular NAE-SAT
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Satisfiability Thresholds for Regular Occupation Problems
• Free Energy Subadditivity for Symmetric Random Hamiltonians
• Waiter-Client and Client-Waiter colourability games on a $k$-uniform hypergraph and the $k$-SAT game
• A Model of Random Industrial SAT