Survey Propagation is an algorithm for random instances of constraint
satisfaction problems. It is derived from the cavity method for the
1-step replica symmetry breaking ansatz in spin glass systems.
We give an alternative view of the algorithm in the case of the SAT
problem. We describe how a SAT formula can be associated with a
novel family of Markov random fields (MRFs), parameterized by a real
number $\rho \in [0,1]$. We then show that applying belief
propagation--a well-known ``message-passing'' technique--to this family of MRFs
recovers various algorithms, ranging from pure survey propagation at one extreme
($\rho = 1$) to standard belief propagation on the uniform distribution
over SAT assignments at the other extreme ($\rho = 0$).
We further discuss experimental and theoretical result arising from the
study of the Markov Random Fields.
Joint work with Elchanan Mossel and Martin Wainwright.

Keywords:

Phase Transition;Computation;Reconstruction

Lecture #10871

Need help? Visit our help pages at http://www.msri.org/communications/vmath/hints

Streaming Video

This is a high quality streaming video encoded with MPEG-4 and with 640x480 resolution.

Windows and Mac users, QuickTime 6.5 or later required
Linux users, please see our Linux Help Page on how to view our streaming videos

Follow this link to --- Watch the Video Now Via Streaming Video ---

Download QuickTime File

You can download the QuickTime file here. Right click on the link and "Save As..." to save to your local computer.

• 10871-10871-QuickTime.mov (141 MB)

Create a DVD

You can download the video and audio files here. Please note that you need both files to create a DVD. Right click on the link and "Save As..." to save to your local computer. You can find instructions on how to create a DVD on our help page at http://www.msri.org/communications/vmath/author

• 10871-10871-DVD PCM Audio.aiff (235 MB - Audio Only)
• 10871-10871-MPEG-2 120min High Quality Encode.m2v (535 MB - Video Only)

Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture.

If you would like to purchase a copy of this video for $15+shipping, please Click Here!

See more of our Streaming Videos on our main VMath - Streaming Video page.