Belief Propagation on the random k-SAT model

2020/11/04 by Coja-Oghlan, Amin, Müller, Noëla, Ravelomanana, Jean B. · 1 citation
#60C05 #68Q87 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2011.02303

Abstract

Corroborating a prediction from statistical physics, we prove that the Belief Propagation message passing algorithm approximates the partition function of the random k-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as "replica symmetry" in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random k-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold.

Cited by

• The random k-SAT Gibbs uniqueness threshold revisited

Related

• The condensation phase transition in the regular k-SAT model
• Belief Propagation on replica symmetric random factor graph models
• A New Look at Survey Propagation and its Generalizations
• One-step replica symmetry breaking of random regular NAE-SAT II
• Proof of the satisfiability conjecture for large k