Belief Propagation on Replica Symmetric Random Factor Graph Models

Authors Amin Coja-Oghlan, Will Perkins



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.27.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Amin Coja-Oghlan
Will Perkins

Cite AsGet BibTex

Amin Coja-Oghlan and Will Perkins. Belief Propagation on Replica Symmetric Random Factor Graph Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.27

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.
Keywords
  • Gibbs distributions
  • Belief Propagation
  • Bethe Free Energy
  • Random k-SAT

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail