Jump to ContentJump to Main Navigation
Statistical Physics, Optimization, Inference, and Message-Passing AlgorithmsLecture Notes of the Les Houches School of Physics: Special Issue, October 2013$
Users without a subscription are not able to see the full content.

Florent Krzakala, Federico Ricci-Tersenghi, Lenka Zdeborova, Riccardo Zecchina, Eric W. Tramel, and Leticia F. Cugliandolo

Print publication date: 2015

Print ISBN-13: 9780198743736

Published to Oxford Scholarship Online: March 2016

DOI: 10.1093/acprof:oso/9780198743736.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 04 April 2020

Cavity method: message-passing from a physics perspective

Cavity method: message-passing from a physics perspective

(p.95) 4 Cavity method: message-passing from a physics perspective
Statistical Physics, Optimization, Inference, and Message-Passing Algorithms

Marc Mézard

Oxford University Press

The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica symmetry breaking (1RSB) levels. This technique has been applied with success to a wide range of models and problems, such as spin glasses, random constraint satisfaction problems (rCSP), and error correcting codes. First, the RS cavity solution for the Sherrington–Kirkpatrick model—a fully connected spin glass model—is derived and its equivalence to the RS solution obtained using replicas is discussed. The general cavity method for diluted graphs is then illustrated at both RS and 1RSB levels. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as an example of an actual problem, k-SAT is investigated using belief and survey propagation.

Keywords:   cavity method, replica method, replica symmetry breaking, Sherrington–Kirkpatrick model, graphical model, random constraint satisfaction problem, belief propagation, survey propagation

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .