Applied Math Seminar: Nick Harvey

The independence polynomial has been widely studied in algebraic graph theory, in statistical physics, and in algorithms for counting and sampling problems. Seminal results of Weitz (2006) and Sly (2010) have shown that in bounded-degree graphs the independence polynomial can be efficiently approximated if the argument is real, positive and below a certain threshold, whereas above that threshold the polynomial is hard to approximate. Furthermore, this threshold exactly corresponds to a phase transition in physics, which demarcates the region within which the Gibbs measure has correlation decay. We consider the problem of computing the independence polynomial with a negative (or even complex) argument, whose magnitude is less than the smallest magnitude of any root of the polynomial. We show that there is a fully-polynomial-time approximation scheme (FPTAS) for such an argument. This result actually holds much more generally for the multivariate independence polynomial, in which each vertex has its own activity. Our proof uses a novel multivariate form of the correlation decay technique. This FPTAS can be used to give a constructive algorithm for the Lovasz Local Lemma in probabilistic combinatorics.