Cavity method: message-passing from a physics perspective

DOI10.1093/ACPROF:OSO/9780198743736.003.0004zbMATH Open1401.82048arXiv1409.3048OpenAlexW1776591594MaRDI QIDQ2990199FDOQ2990199

Authors: Marc Mézard 

Publication date: 29 July 2016

Published in: Statistical Physics, Optimization, Inference, and Message-Passing Algorithms (Search for Journal in Brave)

Abstract: In this three-sections lecture cavity method is introduced as heuristic framework from a Physics perspective to solve probabilistic graphical models and it is presented both at the replica symmetric (RS) and 1-step replica symmetry breaking (1RSB) level. This technique has been applied with success on a wide range of models and problems such as spin glasses, random constrain satisfaction problems (rCSP), error correcting codes etc. Firstly, the RS cavity solution for Sherrington-Kirkpatrick model---a fully connected spin glass model---is derived and its equivalence to the RS solution obtained using replicas is discussed. Then, the general cavity method for diluted graphs is illustrated both at RS and 1RSB level. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as example of an actual problem, K-SAT is investigated using belief and survey propagation.

Full work available at URL: https://arxiv.org/abs/1409.3048

Recommendations

• Solving the spherical \textbf{\(p\)}-spin model with the cavity method: equivalence with the replica results
• Harnessing the Bethe free energy
• Statistical physics and network optimization problems

zbMATH Keywords

graphical modelreplica methodbelief propagationSherrington-Kirkpatrick modelcavity methodreplica symmetry breakingrandom constraint satisfaction problemsurvey propagation

Mathematics Subject Classification ID

Multivariate analysis (62H99) Applications of graph theory (05C90) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Cited In (2)

• The matrix product approximation for the dynamic cavity method
• Solving the spherical \textbf{\(p\)}-spin model with the cavity method: equivalence with the replica results

This page was built for publication: Cavity method: message-passing from a physics perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2990199)