Program

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