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

**Keywords and Mathematics Subject Classification (MSC)**

**Primary Mathematics Subject Classification**No Primary AMS MSC

**Secondary Mathematics Subject Classification**No Secondary AMS MSC

January 13, 2005 | MSRI Program on Probability, Algorithms and Statistical Physics, Spring 2005 --- OPENING DAY, Thursday 13 January, 2005 |

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 |