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