What is the connection between a phase transition in a statistical physics model and the computational complexity of sampling from the given model? In the setting of the hard-core and Potts models on lattices, it is known that in the phase coexistence regime the Glauber dynamics mix slowly. Using some of the same tools used to prove slow mixing (the cluster expansion and Pirogov-Sinai theory), we...