text: Presented on October 2, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116E.
  @cite_17: We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice ( Z ^ d )—heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is torpid or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length L with periodic boundary conditions has upper and lower bounds which are exponential in L d-1. This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in L (log L)2.
  @cite_25: The Ising model is widely regarded as the most studied model of spin-systems in statistical physics. The focus of this paper is its dynamic (stochastic) version, the Glauber dynamics, introduced in 1963 and by now the most popular means of sampling the Ising measure. Intensive study throughout the last three decades has yielded a rigorous understanding of the spectral-gap of the dynamics on ( Z ^2 ) everywhere except at criticality. While the critical behavior of the Ising model has long been the focus for physicists, mathematicians have only recently developed an understanding of its critical geometry with the advent of SLE, CLE and new tools to study conformally invariant systems.
  @cite_8: Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z sup d . We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L sup d-1 . In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point.
summary: In the only two cases so far where the dynamical critical behavior on @math has been addressed---the case @math in @cite_25 and the case of integer @math large enough in @cite_8 @cite_17 ---through the comparison inequalities of Ullrich, the results apply to all Markov chains discussed above (each has @math at @math and @math at @math large enough). Note that the results of @cite_8 @cite_17 are applicable to every dimension @math , while requiring that @math be sufficiently large as a function of @math .