Harnessing the Bethe free energy

Abstract

A wide class of problems in combinatorics, computer science and physics can be described along the following lines. There are a large number of variables ranging over a finite domain that interact through constraints that each bind a few variables and either encourage or discourage certain value combinations. Examples include the $k$-SAT problem or the Ising model. Such models naturally induce a Gibbs measure on the set of assignments, which is characterised by its partition function. The present paper deals with the partition function of problems where the interactions between variables and constraints are induced by a sparse random (hyper)graph. According to physics predictions, a generic recipe called the "replica symmetric cavity method" yields the correct value of the partition function if the underlying model enjoys certain properties [Krzkala et al., PNAS 2007]. Guided by this conjecture, we prove general sufficient conditions for the success of the cavity method. The proofs are based on a "regularity lemma" for probability measures on sets of the form ${\Omega }^n$ for a finite $\Omega$ and a large $n$ that may be of independent interest.

This version replaces version 1 and the RANDOM 2015 version of the paper, which contained critical errors affecting the main results

References in corpus (7)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The asymptotic $k$-SAT threshold
• Counting good truth assignments of random k-SAT formulae
• Maximum independent sets on random regular graphs
• Limits of discrete distributions and Gibbs measures on random graphs
• A positive temperature phase transition in random hypergraph 2-coloring

Cited by in corpus (6)

• Information-theoretic thresholds from the cavity method
• Charting the replica symmetric phase
• Limits of discrete distributions and Gibbs measures on random graphs
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Replica Symmetry Breaking without Replicas
• The number of solutions for random regular NAE-SAT