License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.27
URN: urn:nbn:de:0030-drops-66500
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6650/
Go to the corresponding LIPIcs Volume Portal

Coja-Oghlan, Amin ; Perkins, Will

Belief Propagation on Replica Symmetric Random Factor Graph Models

pdf-format:
LIPIcs-APPROX-RANDOM-2016-27.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{cojaoghlan_et_al:LIPIcs:2016:6650,
  author =	{Amin Coja-Oghlan and Will Perkins},
  title =	{{Belief Propagation on Replica Symmetric Random Factor Graph Models}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6650},
  URN =		{urn:nbn:de:0030-drops-66500},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.27},
  annote =	{Keywords: Gibbs distributions, Belief Propagation, Bethe Free Energy, Random k-SAT}
}

Keywords: Gibbs distributions, Belief Propagation, Bethe Free Energy, Random k-SAT
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI