Belief Propagation on replica symmetric random factor graph models

Amin Coja-Oghlan, Will Perkins

Research output: Chapter in Book/Report/Conference proceedingConference contribution

143 Downloads (Pure)


According to physics predictions, the free energy of random factor graph models that satisfy a certain "static replica symmetry" condition can be calculated via the Belief Propagation message passing scheme [Krzakala et al. PNAS, 2007]. Here we prove this conjecture for a wide class of random factor graph models. Specifically, we show that the messages constructed just as in the case of acyclic factor graphs asymptotically satisfy the Belief Propagation equations and that the free energy density is given by the Bethe free energy formula.
Original languageEnglish
Title of host publicationAPPROX/RANDOM 2016
Publication statusPublished - 7 Sept 2016
EventAPPROX/RANDOM 2016 - Paris, France
Duration: 7 Sept 20169 Oct 2016


ConferenceAPPROX/RANDOM 2016
Internet address


Dive into the research topics of 'Belief Propagation on replica symmetric random factor graph models'. Together they form a unique fingerprint.

Cite this