Abstract

We study the problem of approximating the partition function of the ferromagnetic Ising model on graphs and hypergraphs. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the ``decay of correlations'' property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions.

We first show that in combination with the Lee-Yang theorem, the Patel and Regts framework can be used to give the first polynomial time _deterministic_ approximation algorithm (an FPTAS) for the ferromagnetic Ising model partition function in bounded degree graphs that is valid over the entire range of parameters β (the interaction) and λ (the external field), except for the case |λ|=1 (the ``zero-field'' case). A _randomized_ algorithm (FPRAS) for all graphs, and all β,λ has long been known. Our extension of the Patel and Regts approach, however, extends also to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters (especially in the ``low-temperature'' regime). In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.

Joint work with Alistair Sinclair and Piyush Srivastava.