Home /  Workshop /  Schedule

Schedule, Notes/Handouts & Videos

Phase Transitions in Computation and Reconstruction March 07, 2005 - March 11, 2005

Show All Collapse
Mar 07, 2005
Monday
10:00 AM - 10:50 AM
  Phase Transitions in Reconstruction
Yuval Peres (Microsoft Research)
11:30 AM - 11:50 AM
  Prehistoric Spin Glasses
Jennifer Chayes (UC Berkeley)
12:00 PM - 12:30 PM
  Robust Reconstruction on Trees
Svante Janson (Uppsala University)
02:00 PM - 02:20 PM
  Reconstruction on Regular Trees and the Hard-Core Model
James Martin (University of Oxford)
02:30 PM - 02:50 PM
  Phase Transition in Phylogeny
Elchanan Mossel (Massachusetts Institute of Technology)
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 (Carnegie Mellon University)
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 (Stanford University)
03:30 PM - 03:50 PM
  Proof of the Local REM-Conjecture for Number Partitioning.
Christian Borgs (University of California, Berkeley)
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; University of Washington)
11:00 AM - 11:20 AM
  Applications of the Local Weak Convergence Method to Random Graph Problems
David Gamarnik (Massachusetts Institute of Technology)
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
Back to Workshop