The mixing time of Markov chain Monte Carlo algorithms provides one of the most compelling examples to date of the emerging connection between phase transitions and computational complexity. Roughly speaking, the physical notion of a phase transition frequently has a computational manifestation in the form of a sudden jump in the mixing time.
In this talk I will illustrate the above phenomenon in the special case of the Ising model on trees, and also address the important related issue of the effect of boundary conditions on the mixing time. The techniques we use are quite general, and extend to many other models including the hard-core model (independent sets) and the Potts model (colorings).
This is joint work with Fabio Martinelli and Dror Weitz. No knowledge of statistical physics will be assumed.