Will Perkins

Bethe states of random factor graphs

We present general results on how arbitrary probability distributions on discrete cubes can be approximated by mixtures of product measures. These results are related to and inspired by the decomposition results of Szemeredi and Frieze/Kannan from graph theory. We then apply these results to prove a conjecture of Mezard and Montanari: that Gibbs measures on random factor graphs can be represented as a convex combination of a moderate number of "Bethe states", probability measures which have a simple local and global structure. Based on joint work with Amin Coja-Oghlan.