# Mathematical Sciences Research Institute

Home » Phase Transitions in Computation and Reconstruction

# Workshop

Phase Transitions in Computation and Reconstruction March 07, 2005 - March 11, 2005
 Registration Deadline: March 11, 2005 about 10 years ago December 07, 2004 over 10 years ago
Parent Program: Probability, Algorithms and Statistical Physics
Organizers Dimitris Achlioptas, Elchanan Mossel, Yuval Peres
Speaker(s)

Description

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. Funding & Logistics ## Show Funding To apply for funding, you must register by the funding application deadline displayed above. Students, recent Ph.D.'s, women, and members of underrepresented minorities are particularly encouraged to apply. Funding awards are typically made 6 weeks before the workshop begins. Requests received after the funding deadline are considered only if additional funds become available. ## Show Lodging A block of rooms has been reserved at the Rose Garden Inn. Reservations may be made by calling 1-800-992-9005 OR directly on their website. Click on Corporate at the bottom of the screen and when prompted enter code MATH (this code is not case sensitive). By using this code a new calendar will appear and will show MSRI rate on all room types available. A block of rooms has been reserved at the Hotel Durant. Reservations may be made by calling 1-800-238-7268. When making reservations, guests must request the MSRI preferred rate. If you are making your reservations on line, please go to this link and enter the promo/corporate code MSRI123. Our preferred rate is$129 per night for a Deluxe Queen/King, based on availability.

Additional lodging options (short term housing page - Short Term Housing

## Show Visa/Immigration

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