
Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrak.
arXiv,
July 2016.
PDF.
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 boundeddegree graphs the independence polynomial can be efficiently
approximated if the argument is 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.
Evaluating the independence polynomial with negative or 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 Lovasz 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 roots of the independence
polynomial relate to existence of phase transitions, and there is a relation between negative and
complex roots (Penrose 1963).
We study algorithms for approximating the independence polynomial with negative and complex
arguments. 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
nvertex graph of degree at most d, any α ∈ (0,1], and any complex vector p such
that (1+α)⋅p lies in
Shearer's region, there is a deterministic algorithm to approximate the independence polynomial at p
within (1+ε) multiplicative error and with runtime
(n/εα)^{O(log(d)/α)}.
Our results also extend
to graphs of unbounded degree that have a bounded connective constant. Our analysis uses a novel
multivariate form of the correlation decay technique.
On the hardness side, we prove that every algorithm must have some dependence on α, as it is
#Phard to evaluate the polynomial within any poly(n) factor at an arbitrary given point in Shearer's
region. Similarly, deciding if a given point lies in Shearer's region is also #Phard. Finally, it is NPhard
to approximate the independence polynomial in a graph of degree at most d with a fixed negative
argument that is only a constant factor outside Shearer's region.
