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

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

Abstract

We study an algorithm for approximating the multivariate independence polynomial $Z(\mathbf{z})$, with negative and complex arguments, an object that has strong connections to combinatorics and to statistical physics. In particular, the independence polynomial with negative arguments, $Z(-\mathbf{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. Our algorithm is essentially the same as Weitz's algorithm for positive parameters up to the tree uniqueness threshold, and the core of our analysis is a novel multivariate form of the correlation decay technique, which can handle non-uniform complex parameters. In particular, in the univariate real setting our work implies that Weitz's algorithm works in an interval between two critical points $(\lambda'_c(d), \lambda_c(d))$, and outside of this interval an approximation of $Z(\mathbf{z})$ is known to be NP-hard. As an application, we give a sub-exponential time algorithm for testing approximate membership in the Shearer region. We also give a new rounding based deterministic algorithm for Shearer's lemma (an extension of the LLL), which, however, runs in sub-exponential time. On the hardness side, we prove that evaluating $Z(\mathbf{z})$ at an arbitrary point in Shearer's region, and testing membership in Shearer's region, are #P-hard problems. We also establish the best possible dependence of the exponent of the run time of Weitz's correlation decay technique in the negative regime on the distance to the boundary of the Shearer region.

Introduction

The independence polynomial $Z(z)$ is a fundamental object in combinatorics and statistical physics, representing the generating function of independent sets in a graph. While approximating this polynomial for positive real parameters is well-studied, the problem becomes significantly more difficult when parameters are negative or complex.

These regimes are vital because they connect directly to the Lovász Local Lemma (LLL), a powerful probabilistic tool used to prove the existence of rare combinatorial objects. The Shearer region defines the maximal set of parameters where the LLL can guarantee such a result. Prior to this work, evaluating $Z(z)$ exactly was known to be #P-hard, and existing approximation algorithms suffered from an exponential dependence on the "slack" (how close the parameters are to the boundary of the Shearer region).

The computational landscape of the independence polynomial, showing the FPTAS region established in this work relative to known NP-hard regimes.

Methodology: Multivariate Correlation Decay

The authors employ and significantly refine the correlation decay technique, originally pioneered by Weitz for positive parameters. Key methodological contributions include:

  • Multivariate Analysis: A novel form of the correlation decay technique that can handle non-uniform complex parameters.
  • Error Sensitivity Parameter: Instead of a standard message-passing approach, the authors use a direct amortization argument centered on a new "error sensitivity parameter" ($\beta$). This allows them to track how errors propagate through the recursive computation tree.
  • Improved Decay Rate: The core technical breakthrough is improving the error decay at each step of the recurrence from $(1 - O(\alpha))$ to $(1 - \Omega(\sqrt{\alpha}))$. This improvement reduces the running time's dependence on slack from exponential to sub-exponential.
Visualization of the Shearer region for a simple graph, illustrating the boundary where the independence polynomial remains root-free.

Key Results and Insights

The paper reinforces a deep connection in theoretical computer science: the computational complexity of approximating a partition function is intimately tied to the location of its complex zeros. The Shearer region is precisely the region where the independence polynomial is root-free.

Main Algorithmic Contributions

  1. FPTAS for $Z_G(z)$: A deterministic algorithm to $(1+\epsilon)$-approximate the multivariate independence polynomial in time $(n/\alpha)^{O(\log(d)/\sqrt{\alpha})}$.
  2. Constructive LLL: A deterministic algorithm for the LLL in the "variable model" with running time $(nm/\alpha)^{O(\log(d)\sqrt{m/\alpha})}$. This treats the LLL as a deterministic rounding problem, using approximate polynomial evaluations as "pessimistic estimators" to fix variables one by one.
  3. Membership Testing: An algorithm to decide if a parameter vector $p$ is in the Shearer region (within a multiplicative error of $1+\alpha$) in time $(n/\alpha)^{O(\sqrt{n/\alpha} \log d)}$.

Complexity Barriers

The authors prove that exactly evaluating $Z(z)$ at an arbitrary point in the Shearer region and testing membership in the region are both #P-hard problems. Furthermore, they show that the $1/\sqrt{\alpha}$ dependence in the exponent is likely optimal for any technique based on Weitz’s correlation decay framework.

Conclusion and Future Work

While $1/\sqrt{\alpha}$ is a significant improvement over $1/\alpha$, the algorithm is still not "fully" polynomial as the exponent grows as the slack $\alpha$ shrinks. A major open question is whether an algorithm exists with a running time independent of $1/\alpha$ in the exponent. Breaking this sub-exponential barrier might require moving away from correlation decay toward sampling-based methods like Markov Chain Monte Carlo (MCMC). However, no natural "Gibbs distribution" is currently known for the negative activity setting.

Summary updated

Abstract

We study an algorithm for approximating the multivariate independence polynomial $Z(\mathbf{z})$, with negative and complex arguments, an object that has strong connections to combinatorics and to statistical physics. In particular, the independence polynomial with negative arguments, $Z(-\mathbf{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. Our algorithm is essentially the same as Weitz's algorithm for positive parameters up to the tree uniqueness threshold, and the core of our analysis is a novel multivariate form of the correlation decay technique, which can handle non-uniform complex parameters. In particular, in the univariate real setting our work implies that Weitz's algorithm works in an interval between two critical points $(\lambda'_c(d), \lambda_c(d))$, and outside of this interval an approximation of $Z(\mathbf{z})$ is known to be NP-hard. As an application, we give a sub-exponential time algorithm for testing approximate membership in the Shearer region. We also give a new rounding based deterministic algorithm for Shearer's lemma (an extension of the LLL), which, however, runs in sub-exponential time. On the hardness side, we prove that evaluating $Z(\mathbf{z})$ at an arbitrary point in Shearer's region, and testing membership in Shearer's region, are #P-hard problems. We also establish the best possible dependence of the exponent of the run time of Weitz's correlation decay technique in the negative regime on the distance to the boundary of the Shearer region.
BibTeX
@misc{harvey2016computing,
  author = {Nicholas J. A. Harvey and Piyush Srivastava and Jan Vondrák},
  title = {{Computing the independence polynomial in Shearer's region for the LLL}},
  year = {2016},
  eprint = {1608.02282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1608.02282},
}
Figure