The random 2-SAT partition function

Abstract

We show that throughout the satisfiable phase the normalised number of satisfying assignments of a random $2$-SAT formula converges in probability to an expression predicted by the cavity method from statistical physics. The proof is based on showing that the Belief Propagation algorithm renders the correct marginal probability that a variable is set to `true' under a uniformly random satisfying assignment.

References in corpus (18)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Ising models on locally tree-like graphs
• The Scaling Window of the 2-SAT Transition
• An Extended Variational Principle for the SK Spin-Glass Model
• Statistical mechanics of the random K-SAT model
• The Entropy of the K-Satisfiability Problem
• Information-theoretic thresholds from the cavity method
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• The asymptotic $k$-SAT threshold
• Spin glass models from the point of view of spin distributions
• Factor models on locally tree-like graphs
• The Satisfiability Threshold for k-XORSAT
• Counting good truth assignments of random k-SAT formulae
• Replica bounds for optimization problems and diluted spin systems
• Proof of the satisfiability conjecture for large k
• The replica symmetric phase of random constraint satisfaction problems
• On the replica symmetric solution of the K-sat model

Cited by in corpus (1)

• Scale-Free Random SAT Instances