Local Weak Convergence method (LWC) exploits local structure (typically a tree) of a large
random combinatorial object and leads to a complete asymptotic solution to several optimization
problems on random graphs. The method reduces the original problem into the problem of finding
fixed points of a certain distributional operator. We show that when the fixed point of the second iterate of the distributional operator is unique, it determines asymptotically the value of the underlying combinatorial optimization problem.
We demonstrate this on a problem of finding maximum weighted independent set in a sparse random graph. We further show that the uniqueness of the fixed point of the distributional operator is tightly related to the correlation decay and high temperature/low regimes in statistical physics models.
Joint work with Tomasz Nowicki and Grzegorz Swirszcz

Keywords:

Phase Transitions; computation;reconstruction

Lecture #10875

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.

• 10875-10875-QuickTime.mov (188 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

• 10875-10875-DVD PCM Audio.aiff (300 MB - Audio Only)
• 10875-10875-MPEG-2 120min High Quality Encode.m2v (685 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.