Phase Transitions and Sampling

Allan Sly, UC Berkeley Statistics

February 15th, 2012 at 4PM–5PM in 939 Evans Hall [Map]

I will discuss two recent pieces of work relating phases transitions of spin-systems to questions of sampling their distributions.

1. For the heat bath Glauber dynamics for the two dimensional Ising model, the growth of the mixing time is now known at all temperatures. The final case was at the critical temperature which was completed using new ideas from the study of SLE.
2. The question of what relationships exist between phase transitions in statistical physics and the computational complexity of sampling and counting has been of ongoing interest in theoretical computer science. Recent progress has established the computational complexity of sampling on d-regular graphs for essentially all 2-spin systems. The complexity depends on whether the model has a unique Gibbs measure on the infinite d-regular tree establishing the equivalence of phase transitions and computational thresholds in these cases.