Mathematical Sciences Research Institute - Probability, Algorithms and Statistical Physics

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

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.'

Workshops for this Program:

MSRI Program on Probability, Algorithms and Statistical Physics, Spring 2005 --- OPENING DAY, Thursday 13 January, 2005
January 13, 2005 to January 13, 2005
Markov Chains in Algorithms and Statistical Physics
January 31, 2005 to February 4, 2005
Phase Transitions in Computation and Reconstruction
March 7, 2005 to March 11, 2005
Models of Real-World Random Networks
April 18, 2005 to April 22, 2005

Questions about this program should be sent either by email to the Program Coordinator or by regular mail to:

Probability, Algorithms and Statistical Physics Mathematical Sciences Research Institute 17 Gauss Way, Berkeley, CA 94720-5070. USA

Back to Program Listing

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