Mathematical Sciences Research Institute - Phase Transitions in Computation and Reconstruction

Phase transition is qualitative change in a system due to a small quantitative change of a parameter. Outside physics, such transitions have been empirically observed in diverse areas such as computational complexity, congestion phenomena and optimization.

The topics of this workshop include phase transitions in connection to random graphs, boolean functions, satisfiability problems, coding, reconstruction on trees and spinglasses.

Special focus will be given to the study of the interplay between the replica method, local weak convergence and algorithmic aspects of reconstruction.

A .pdf file is available with a list of speaker names and the title of their lecture.

Tentative Workshop Schedule
All sessions will be held in the Second Floor lecture Hall

Mon. March 7
9:45 Welcome
10-10:50 1. Yuval Peres (Berkeley): Phase Transitions in Reconstruction
11-11:30 coffee
11:30-11:50 2. Jennifer Chayes (Microsoft):Prehistoric Spin Glasses
12:00-12:20 3. James Martin (Jussieu & MSRI):Reconstruction on regular trees and the hard-core model
12:30-14:00 Lunch
14:00-14:20 4. Alistair Sinclair (Berkeley):Reconstruction problems on trees: a simple criterion for impossibility
14:30-14:50 5. Svante Janson: Robust Reconstruction on trees
15:00-16:00 Break
16:00-16:50 6. Friedgut (Evans-MSRI) talk:Hunting for Sharp Thresholds

Tue. March 8
9:30-9:50 7. Elchanan Mossel (Berkeley):
Phase transition in Phylogeny
10:00-10:20 8. David Levin (Utah & MSRI):Phase transition in reconstructing bias of bit sequences
10:30-11:00 Coffee
11:00-11:20 9. Mike Molloy (Toronto):Sharp thresholds for random constraint satisfaction problems
11:30-11:50 10. Ryan O'Donnell (Microsoft):Correlation Distillation On Trees
12:00-14:00 Lunch
14:00-14:20 11. Krzysztof Oleszkiewicz (Warsaw):An invariance principle, with some applications to Boolean functions
14:30-14:50 12. Sourav Chatterjee (Stanford):Universality results: A general approach
15:00-15:30 Coffee
15:30-15:50 13. Christian Borgs (Microsoft):Proof of the local REM-conjecture for number partitioning
16:00-16:40 14. B\'ela Bollob\'as (Memphis): Random Voronoi Percolation in the Plane

Wed. March 9
9:30-10:20 15. Riccardo Zecchina (ICTP):TBA
10:30-11:00 Coffee
11:00-11:20 16. Elitza Maneva (Berkeley):An alternative view of Survey Propagation for satisfiability
11:30-11:50 17. Balaji Prabhakar (Stanford):The asymptotic behavior of minimal matchings in the random assignment problem
12:00-12:20 18. Devavrat Shah (MSRI & MIT):Belief Propagation for finding Max Weight Matching

Thu. March 10
9:30-10:20 19. David Aldous (Berkeley):Local weak convergence and the cavity method
10:30-11:00 Coffee
11:00-11:20 20. David Gamarnik (IBM):Applications of the local weak convergence method to random graph problems
11:30-11:50 21. Greg Sorkin (IBM):A linear-expected-time algorithm for Max Cut on sparse random graphs
12:00-14:00 Lunch
14:00-14:20 22. Rick Kenyon (UBC):Simple random surfaces
14:30-14:50 23. Robin Pemantle (UPENN):The best path in a tree is hard to find
15:00-15:30 Coffee
15:30-15:50 24. Van Vu (UCSD):(Sharp) thresholds for random regular graphs

Fri. March 11
9:30-10:20 25. Marc Mezard (Paris Sud and MSRI): Hard constraints on random graphs: from lattice glasses to matching problems
10:30-11:00 Coffee
11:00-11:20 26. Dimitris Achlioptas:Random formulas have frozen variables
11:30-11:50 27. Andrea Montanari (Paris Sud and MSRI):Phase Transitions in Iterative Coding Systems
12:00-14:00 Lunch
14:00-14:20 28. Vladas Sidoravicius (IMPA & MSRI):TBA
14:30-14:50 30. David Revelle (Berkeley):Mixing times for random walks on finite lamplighter groups
15:00-15:30 Coffee
15:30-15:50 31. Roman Kotecky (Charles University and Microsoft):Phase coexistence and collapse of supersaturation

Lodging:
Rooms for this workshop are being held at the Rose Garden Inn at the special rate of $99/night, plus tax. To make reservations, please send an e-mail to: rosegardengm@aol.com. The cut-off date for reservations is Feb. 6!

For alternative, short-term accommodations, click here.

Follow this link to read about the new U.S. visa requirements

Currently Available Videos

Yuval Peres , Phase Transitions in Reconstruction March 7,2005, 10:00 AM to 10:50 AM
Jennifer Chayes , Prehistoric Spin Glasses March 7,2005, 11:30 AM to 11:50 AM
Svante Janson , Robust Reconstruction on Trees March 7,2005, 12:00 PM to 12:30 PM
James Martin , Reconstruction on Regular Trees and the Hard-Core Model March 7,2005, 02:00 PM to 02:20 PM
Elchanan Mossel , Phase Transition in Phylogeny March 7,2005, 02:30 PM to 02:50 PM
Alistair Sinclair , Recontruction Problems on Trees: A Simple Criterion for Impossibility March 8,2005, 09:30 AM to 09:50 AM
David Levin , Phase Transition in Reconstructing Bias of Bit Sequences March 8,2005, 10:00 AM to 10:20 AM
Mike Molloy , Sharp Thresholds for Random Constraint Satisfaction Problems March 8,2005, 11:00 AM to 11:20 AM
Ryan O'Donnell , Correlation Distillation On Trees March 8,2005, 11:30 AM to 11:50 AM
Krzysztof Oleszkiewicz , An Invariance Principle, with Some Applications to Boolean Functions March 8,2005, 02:00 PM to 02:20 PM
Sourav Chatterjee , Universality results: A General Approach March 8,2005, 02:30 PM to 02:50 PM
Christian Borgs , Proof of the Local REM-Conjecture for Number Partitioning. March 8,2005, 03:30 PM to 03:50 PM
, Random Voronoi Percolation in the Plane March 8,2005, 04:00 PM to 04:40 PM
Riccardo Zecchina , "1-RSB" Clustering and Algorithms for Random Constraint Satisfaction Problems March 9,2005, 09:30 AM to 10:20 AM
Elitza Maneva , An Alternative View of Survey Propagation for Satisfiability March 9,2005, 11:00 AM to 11:20 AM
Balaji Prabhakar , The Asymptotic Behavior of Minimal Matchings in the Random Assignment Problem March 9,2005, 11:30 AM to 11:50 AM
, Belief Propagation for finding Max Weight Matching March 9,2005, 12:00 PM to 12:20 PM
David Aldous , Local Weak Convergence and the Cavity Method March 10,2005, 09:30 AM to 10:20 AM
David Gamarnik , Applications of the Local Weak Convergence Method to Random Graph Problems March 10,2005, 11:00 AM to 11:20 AM
Gregory Sorkin , A Linear-Expected-Time Algorithm for Max Cut on Sparse Random Graphs March 10,2005, 11:30 AM to 11:50 AM
Richard Kenyon , Simple Random Surfaces March 10,2005, 02:00 PM to 02:20 PM
David Revelle , Mixing Times for Random Walks on Finite Lamplighter March 10,2005, 03:30 PM to 03:50 PM
Van Vu , (Sharp) Thresholds for Random Regular Graphs March 10,2005, 03:50 PM to 04:20 PM
Raissa D'Souza , Novel Behavior in a Simple Cellular Automaton Model of Traffic March 10,2005, 04:20 PM to 04:50 PM
Marc Mezard , Hard Constraints on Random Graphs: From Lattice Glasses to Matching Problems March 11,2005, 09:30 AM to 10:20 AM
Dimitris Achlioptas , Random Formulas Have Frozen Variables March 11,2005, 11:00 AM to 11:20 AM
Andrea Montanari , Phase Transitions in Iterative Coding Systems March 11,2005, 11:30 AM to 11:50 AM
Roman Kotecky , Phase Coexistence and Collapse of Supersaturation March 11,2005, 02:00 PM to 02:20 PM
Vladas Sidoravicius , A Few Problems Related to Percolation of Binary Sequences March 11,2005, 02:30 PM to 02:50 PM

You can find videos of other workshops and events on our VMath - Streaming Video page.

For more information:
Questions about this workshop should be sent either by email to

272@msri.org

or by regular mail to:

Phase Transitions in Computation and Reconstruction Mathematical Sciences Research Institute 17 Gauss Way, Berkeley, CA 94720-5070. USA

The Institute is committed to the principles of Equal Opportunity and Affirmative Action.

Back to Workshop Listing

Want to be kept updated on upcoming events? Then Click Here to Subscribe to Our Newsletters!