Belief Propagation on replica symmetric random factor graph models

Amin Coja-Oghlan, Will Perkins

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

160 Downloads (Pure)

Abstract

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
DOIs
Publication statusPublished - 7 Sept 2016
EventAPPROX/RANDOM 2016 - Paris, France
Duration: 7 Sept 20169 Oct 2016
http://cui.unige.ch/tcs/random-approx/2016/index.php

Conference

ConferenceAPPROX/RANDOM 2016
Country/TerritoryFrance
CityParis
Period7/09/169/10/16
Internet address

Fingerprint

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

Cite this