title: 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 thek-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) 10318-10323]. 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 Ωn for a finite Ω and a largenthat may be of independent interest. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 694-741, 2016.
authors.affiliation: Goethe University, Mathematics Institute Frankfurt 60325 Germany.
authors.forename: Victor
authors.initials: V
authors.lastname: Bapst
authors.affiliation: Goethe University, Mathematics Institute Frankfurt 60325 Germany.
authors.forename: Amin
authors.initials: A
authors.lastname: Coja-Oghlan
keywords: Belief Propagation; cavity method; random graphs; regularity lemma