Algorithmic Pirogov-Sinai theory

DOI10.1145/3313276.3316305MaRDI QIDQ5212841zbMATH OpenOpenAlexFDO

Authors Tyler Helmuth, Will Perkins, Guus Regts

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.11548

approximate counting algorithms hard-core model Pirogov-Sinai theory Potts model sampling algorithms statistical physics

Mathematics Subject Classification ID

Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Statistical mechanics of magnetic materials (82D40) Basic methods in statistical mechanics (82M99)

Abstract: 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

m a t h b b Z^{d}

and on the torus

(m a t h b b Z / n m a t h b b Z)^{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

m a t h b b Z^{d}

with appropriate boundary conditions and an efficient sampling algorithm for the ferromagnetic Potts model on the discrete torus

(m a t h b b Z / n m a t h b b Z)^{d}

at sufficiently low temperature.

Recommendations

Cited in

(37)

This page was built for publication: Algorithmic Pirogov-Sinai theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212841)