The condensation phase transition in the regular k-SAT model

2015/07/13 by Bapst, Victor, Coja-Oghlan, Amin
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1507.03512

Abstract

Much of the recent work on random constraint satisfaction problems has been inspired by ingenious but non-rigorous approaches from physics. The physics predictions typically come in the form of distributional fixed point problems that are intended to mimic Belief Propagation, a message passing algorithm, applied to the random CSP. In this paper we propose a novel method for harnessing Belief Propagation directly to obtain a rigorous proof of such a prediction, namely the existence and location of a condensation phase transition in the random regular k-SAT model.

Related

• Belief Propagation on the random k-SAT model
• Local geometry of NAE-SAT solutions in the condensation regime
• Exact Phase Transitions in Random Constraint Satisfaction Problems
• One-step replica symmetry breaking of random regular NAE-SAT II
• One-step replica symmetry breaking of random regular NAE-SAT I