The main themes of the special semester will be: 1. Mixing of Markov chains in physics and algorithms Development of analytical tools for the analysis of mixing times of Markov chains; applications to randomized algorithms for approximate counting, combinatorial optimization. Relationship between mixing times, spatial properties of Gibbs measures, and the geometry of the underlying graphs. 2. Phase transitions in computation and reconstruction Identification of phase transitions in a wide variety of contexts, including noisy computation, random graphs, satisfiability problems, reconstruction problems on trees, and hidden Markov models; rigorous connections between such models and models in statistical physics; combinatorial optimization with random inputs; self-organized criticality and invasion percolation. Noise sensitivity of Boolean functions. 3. Models of real-world random networks Development of more realistic mathematical models for complex networks, such as the Internet, telephone networks, and social structures; exploration of the detailed properties of such models; study of dynamical processes on complex networks. Workshops on each of these themes are planned.
During the special semester, apart from the workshops, two regular seminars will be held: a research seminar where program participants will present new results, and an expository seminar accessible to graduate students. The hexagon tiling below was generated by David B. Wilson using a Markov chain on the space of tilings, and an exact sampling technique known as 'coupling from the past.'
|January 31, 2005 - February 04, 2005||Markov Chains in Algorithms and Statistical Physics|
|March 07, 2005 - March 11, 2005||Phase Transitions in Computation and Reconstruction|
|April 18, 2005 - April 22, 2005||Models of Real-World Random Networks|
|January 13, 2005||MSRI Program on Probability, Algorithms and Statistical Physics, Spring 2005 --- OPENING DAY, Thursday 13 January, 2005|