The random k-SAT Gibbs uniqueness threshold revisited

2025/06/02 by Chatterjee, Arnab, Coja-Oghlan, Amin, Greenhill, Catherine +4
#60C05 #68Q87 #68R07 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2506.01359

Abstract

We prove that for any k≥3 for clause/variable ratios up to the Gibbs uniqueness threshold of the corresponding Galton-Watson tree, the number of satisfying assignments of random k-SAT formulas is given by the `replica symmetric solution' predicted by physics methods [Monasson, Zecchina: Phys. Rev. Lett. (1996)]. Furthermore, while the Gibbs uniqueness threshold is still not known precisely for any k≥3, we derive new lower bounds on this threshold that improve over prior work [Montanari and Shah: SODA (2007)].The improvement is significant particularly for small k.

Citations

• On the Replica Symmetric Solution in General Diluted Spin Glasses
• Improved Bounds for Sampling Solutions of Random CNF Formulas
• Fast sampling of satisfying assignments from random k-SAT with applications to connectivity
• The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
• Belief Propagation on the random k-SAT model
• The number of satisfying assignments of random regular k-SAT formulas
• Belief Propagation on replica symmetric random factor graph models
• On the concentration of the number of solutions of random satisfiability\n formulas
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model

Related

• The random italic k k k -SAT Gibbs uniqueness threshold revisited
• Proof of the satisfiability conjecture for large k
• Bounds on Threshold of Regular Random k-SAT
• On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
• On the Regularity of Random 2-SAT and 3-SAT