Belief propagation on the random k-SAT model
Amin Coja‐Oghlan, Noëla Müller, Jean Bernoulli Ravelomanana · The Annals of Applied Probability · 2022
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.