We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters &#x03B2; (the interaction) and &#x03BB; (the external field), except for the case |&#x03BB;|=1 (the zero-field case). A randomized algorithm (FPRAS) for all graphs, and all &#x03B2;,&#x03BB; has long been known. 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. Our approach extends 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. 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.
In a parallel line of work, Barvinok initiated the study of Taylor approximation of the logarithm of the partition function, which led to quasipolynomial time approximation algorithms for a variety of counting problems @cite_16 @cite_42 @cite_35 @cite_27 . More recently, Patel and Regts @cite_5 showed that for several models that can be written as induced subgraph sums, one can actually obtain an FPTAS from this approach. In particular, for problems such as counting independent sets with negative (or, more generally, complex valued) activities on bounded degree graphs, they were able to match the range of applicability of existing algorithms based on correlation decay, and were also able to extend the approach to Tutte polynomials and edge-coloring models (also known as Holant problems) where little is known about correlation decay.
@cite_35 @cite_42 @cite_27 @cite_5 @cite_16
2963364787 2962992138 2474151873 1997999115
We present a deterministic algorithm which, given a graph G with n vertices and an integer 1 0 is an absolute constant. This allows us to tell apart the graphs that do not have m-subsets of high density from the graphs that have sufficiently many m-subsets of high density, even when the probability to hit such a subset at random is exponentially small in m. ACM Classification: F.2.1, G.1.2, G.2.2, I.1.2 AMS Classification: 15A15, 68C25, 68W25, 60C05 Abstract We consider a refinement of the partition function of graph homomorphisms and present a quasi-polynomial algorithm to compute it in a certain domain. As a corollary, we obtain quasi-polynomial algorithms for computing partition functions for independent sets, perfect matchings, Hamiltonian cycles and dense subgraphs in graphs as well as for graph colorings. This allows us to tell apart in quasi-polynomial time graphs that are sufficiently far from having a structure of a given type (i.e., independent set of a given size, Hamiltonian cycle, etc.) from graphs that have sufficiently many structures of that type, even when the probability to hit such a structure at random is exponentially small. In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polynomials @math and show that if @math and there is a disk @math centered at zero in the complex plane such that @math does not vanish on @math for all bounded degree graphs @math , then for each @math in the interior of @math there exists a deterministic polynomial-time approximation algorithm for evaluating @math at @math . This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated b... We present a deterministic algorithm, which, for any given @math 0<∈<1 and an @math n×n real or complex matrix @math A=aij such that @math aij-1≤0.19 for all @math i,j computes the permanent of @math A within relative error @math ∈ in @math nOlnn-ln∈ time. The method can be extended to computing hafnians and multidimensional permanents.