Lecture

Survey Propagation: Cavity Method

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

PHYS-642: Statistical physics for optimization & learning

This course covers the statistical physics approach to computer science problems, with an emphasis on heuristic & rigorous mathematical technics, ranging from graph theory and constraint satisfaction to inference to machine learning, neural networks and st ...

Description

This lecture covers the Survey Propagation algorithm, focusing on the Cavity Method and its application in solving constraint satisfaction problems. The instructor explains the iterative message-passing process and the concept of excess degree. The lecture also delves into the Survey Propagation algorithm's performance and its relation to the Berry Froom property.

Instructors (2)

Florent Gérard Krzakala

Lenka Zdeborová

Lenka Zdeborová is a Professor of Physics and of Computer Science in École Polytechnique Fédérale de Lausanne where she leads the Statistical Physics of Computation Laboratory. She received a PhD in physics from University Paris-Sud and from Charles University in Prague in 2008. She spent two years in the Los Alamos National Laboratory as the Director's Postdoctoral Fellow. Between 2010 and 2020 she was a researcher at CNRS working in the Institute of Theoretical Physics in CEA Saclay, France. In 2014, she was awarded the CNRS bronze medal, in 2016 Philippe Meyer prize in theoretical physics and an ERC Starting Grant, in 2018 the Irène Joliot-Curie prize, in 2021 the Gibbs lectureship of AMS. She is an editorial board member for Journal of Physics A, Physical Review E, Physical Review X, SIMODS, Machine Learning: Science and Technology, and Information and Inference. Lenka's expertise is in applications of concepts from statistical physics, such as advanced mean field methods, replica method and related message-passing algorithms, to problems in machine learning, signal processing, inference and optimization. She enjoys erasing the boundaries between theoretical physics, mathematics and computer science.

Official source

Related concepts (30)

Constraint satisfaction problem

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families.

Constraint satisfaction

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered.

Cavity method

The cavity method is a mathematical method presented by Marc Mézard, Giorgio Parisi and Miguel Angel Virasoro in 1987 to solve some mean field type models in statistical physics, specially adapted to disordered systems. The method has been used to compute properties of ground states in many condensed matter and optimization problems. Initially invented to deal with the Sherrington–Kirkpatrick model of spin glasses, the cavity method has shown wider applicability.

Constraint programming

Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found.

Hangul

The Korean alphabet, known as Hangul (ˈhɑːnguːl ; ) in South Korea and Chosŏn'gŭl () in North Korea, is the modern official writing system for the Korean language. The letters for the five basic consonants reflect the shape of the speech organs used to pronounce them, and they are systematically modified to indicate phonetic features; similarly, the vowel letters are systematically modified for related sounds, making Hangul a featural writing system.

Related lectures (6)

B. Ananthanarayan (IISc) - Analyticity, Unitarity, Crossing: An Introduction - IV

Scaling & Renormalization in Statistical Mechanics

Explores scaling and renormalization in statistical mechanics, emphasizing critical points and invariant properties.

Simplex Algorithm

Covers the Simplex algorithm for function minimization with linear constraints.

Optimal Control: Convergence and Conditions

Covers the convergence and conditions for optimal control.

Information Theory: Entropy and Capacity