We study an algorithm for approximating the multivariate independence polynomial Z(z), with negative and complex arguments. While the focus so far has been mostly on computing combinatorial polynomials restricted to the univariate positive setting (with seminal results for the independence polynomial by Weitz (2006) and Sly (2010)), the independence polynomial with negative or complex arguments has strong connections to combinatorics and to statistical physics. The independence polynomial with negative arguments, Z(-p), determines the Shearer region, the maximal region of probabilities to which the Lovasz Local Lemma (LLL) can be extended (Shearer 1985). In statistical physics, complex zeros of the independence polynomial relate to existence of phase transitions. Our main result is a deterministic algorithm to compute approximately the independence polynomial in any root-free complex polydisc centered at the origin. More precisely, we can (1 + ε)-approximate the independence polynomial Z(z) for an n-vertex graph of degree at most d, for any complex vector z such that Z(z') ≠ 0 for |z'_i| ≤ (1 + α)|z_i|, in running time (n/εα)~(O(log(d)/{the square root of}α)). Our result also extends to graphs of unbounded degree that have a bounded connective constant. Our algorithm is essentially the same as Weitz's algorithm for positive parameters up to the tree uniqueness threshold. The core of the analysis is a novel multivariate form of the correlation decay technique, which can handle non-uniform complex parameters. In summary, we provide a unifying algorithm for all known regions where Z(z) is approximately computable. In particular, in the univariate real setting our work implies that Weitz's algorithm works in an interval between two critical points (-λ'_c(d), λ_c(d)), and outside of this interval an approximation of Z(λ) is known to be NP-hard. As an application, we provide an algorithm to test membership in Shearer's region within a multiplicative error of 1 + α, in running time (n/α)~(O({the square root of}(n/α) log d)). We also give a deterministic algorithm for Shearer's lemma (extending the LLL) with n events on m independent variables under slack α, with running time (nm/α)~(O({the square root of}(m/α)log d)). On the hardness side, we prove that evaluating Z(z) at an arbitrary point in Shearer's region, and testing membership in Shearer's region, are #P-hard problems. For Weitz's correlation decay technique in the negative regime, we show that the 1/{the square root of}α dependence in the exponent is optimal.
展开▼
