The condensation phase transition in the regular k SAT model
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.
APPROX RANDOM