Belief Propagation on the random $k$-SAT model

Amin Coja-Oghlan, Noëla Müller, Jean B. Ravelomanana

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…