Home » Probability, algorithms and statistical physics

Program

Probability, Algorithms and Statistical Physics January 03, 2005 to May 15, 2005

Organizers Yuval Peres (co-chair), Alistair Sinclair (co-chair), David Aldous, Claire Kenyon, Harry Kesten, Jon Kleinberg, Fabio Martinelli, Alan Sokal, Peter Winkler, Uri Zwick

Description In the last decade, key notions from statistical physics, such as 'phase transition' and 'critical exponents' are being applied to a variety of questions in computational complexity, the analysis of algorithms, and real-world random networks. Conversely, techniques developed by combinatorialists and computer scientists to analyze randomized algorithms, have been adopted by probabilists and mathematical physicists to study particle systems and other stochastic physical models. We believe that the insights resulting from the interaction of mathematical physicists, probabilists and computer scientists should lead to further advances both in the development of these techniques and in new applications.
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.'

Logistics Program Logistics can be viewed by Members. If you are a program member then Login Here.

Programmatic Workshops

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