Computing the independence polynomial in Shearer's region for the LLL

Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák

Published 2016-08-07Version 1

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 the that the computational complexity of approximating the independence polynomial with positive activities is tightly linked to a uniqueness phase transition for a Gibbs measure. We study algorithms for approximating the independence polynomial with negative and complex arguments. The independence polynomial with complex arguments may not have a counting interpretation, but it does have strong connections to combinatorics and to statistical physics. The independence polynomial with negative arguments determines the maximal region of probabilities to which the Lov\'{a}sz Local Lemma (LLL) can be extended, and also gives a lower bound on the probability in the LLL's conclusion (Shearer 1985). In statistical physics, complex (and negative) zeros of the independence polynomial relate to existence of phase transitions (Penrose 1963). Whereas many algorithms for computing combinatorial polynomials are restricted to the univariate setting, we consider the multivariate independence polynomial, since there is a natural multivariate region of interest -- Shearer's region for the LLL. Our main result is: for any $n$-vertex graph of degree at most $d$, any $\alpha \in (0,1]$, and any complex vector $p$ such that $(1+\alpha) \cdot p$ lies in Shearer's region, there is a deterministic algorithm to approximate the independence polynomial at $p$ within $(1+\epsilon)$ multiplicative error and with runtime $(\frac{n}{\epsilon \alpha})^{O(\log(d)/\alpha)}$. Our results also extend to graphs of unbounded degree that have a bounded connective constant. We also give hardness results addressing the dependence of the runtime of the algorithm on the above parameters.