I'll describe a general way to efficiently approximate the partition function in a complex domain, provided it has no zeros in a slightly larger domain. Examples include (multi-dimensional) permanents counting (hypergraph) perfect matchings and hafnians counting perfect matchings in general (non-bipartite) graphs, graph homomorphism partition function and its refinements, (hypergraph) matching polynomial, etc. Although typically the method results in quasi-polynomial algorithms, Patel and Regts have shown that the algorithms can be made genuinely polynomial time on bounded degree graphs. In most cases, the interpolation approach matches or appears to outperform the correlation decay method, although until recently the interpolation approach was lagging behind the correlation decay method in the notable case of the independence polynomial of a graph. The recent proof by Peters and Regts of the Sokal conjecture implies that both approaches produce the same approximation (Weitz' bound) for the independence polynomial.
Monday, June 5th, 2017
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.
We show that for certain classes of posets, biased Markov chains that walk along edges of their Hasse diagrams can be used to approximately generate samples with any fixed rank in expected polynomial time. A noteworthy application of our method is sampling restricted classes of integer partitions of n. We give the first provably efficient Markov chain algorithm to uniformly sample integer partitions of n from various natural restricted classes. Related applications include sampling permutations with a fixed number of inversions and lozenge tilings on the triangular lattice with a fixed average height.
Tuesday, June 6th, 2017
Wednesday, June 7th, 2017
Thursday, June 8th, 2017