Author name cluster

Tyler Helmuth

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

STOC Conference 2020 Conference Paper

Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures

Christian Borgs
Jennifer T. Chayes
Tyler Helmuth
Will Perkins 0001
Prasad Tetali

For d ≥ 2 and all q ≥ q 0 ( d ) we give an efficient algorithm to approximately sample from the q -state ferromagnetic Potts and random cluster models on the torus (ℤ / n ℤ ) d for any inverse temperature β≥ 0. This stands in contrast to Markov chain mixing time results: the Glauber dynamics mix slowly at and below the critical temperature, and the Swendsen–Wang dynamics mix slowly at the critical temperature. We also provide an efficient algorithm (an FPRAS) for approximating the partition functions of these models.

Details

STOC Conference 2019 Conference Paper

Algorithmic Pirogov-Sinai theory

Tyler Helmuth
Will Perkins 0001
Guus Regts

We develop an efficient algorithmic approach for approximate counting and sampling in the low-temperature regime of a broad class of statistical physics models on finite subsets of the lattice ℤ d and on the torus (ℤ/ n ℤ) d . Our approach is based on combining contour representations from Pirogov–Sinai theory with Barvinok’s approach to approximate counting using truncated Taylor series. Some consequences of our main results include an FPTAS for approximating the partition function of the hard-core model at sufficiently high fugacity on subsets of ℤ d with appropriate boundary conditions and an efficient sampling algorithm for the ferromagnetic Potts model on the discrete torus (ℤ/ n ℤ) d at sufficiently low temperature.

Details