This paper explores the computational boundaries of the independence polynomial, a central object in both combinatorics and statistical physics. The authors provide a deterministic algorithm to approximate this polynomial even when its variables are negative or complex—a regime that is notoriously difficult but deeply connected to the Lovász Local Lemma (LLL).
TL;DR
The authors present a deterministic FPTAS (Fully Polynomial Time Approximation Scheme) for the multivariate independence polynomial in the "Shearer region," where the polynomial is guaranteed to be root-free. This result provides a unifying algorithmic framework for the Lovász Local Lemma and establishes that the computational complexity of the polynomial undergoes a phase transition exactly at the boundary of this region.
What Problem Does This Paper Address?
The independence polynomial $Z(G, \mathbf{z})$ of a graph $G$ is the generating function of its independent sets. In statistical physics, it is known as the partition function of the "hard-core lattice gas" model.
While approximating this polynomial for positive real activities is well-understood (thanks to Weitz’s 2006 work on correlation decay), the case for negative or complex activities remained a major challenge. This isn't just a theoretical curiosity:
- Combinatorics: The region where the polynomial has no roots (the Shearer region) defines the maximum possible range of probabilities for which the Lovász Local Lemma—a tool used to prove the existence of rare combinatorial objects—can be applied.
- Physics: Complex zeros of partition functions are directly related to phase transitions (Lee-Yang theory).
The authors tackle the problem of efficiently approximating $Z(\mathbf{z})$ when $\mathbf{z}$ lies within this Shearer region, and they investigate the computational hardness of the problem as one approaches the region's boundary.
Methods
The paper builds on Weitz’s correlation decay technique, which uses a recursive tree-like structure to compute "occupation ratios" (the likelihood of a vertex being in an independent set).
The key methodological innovations include:
- Multivariate Correlation Decay: Unlike previous work that focused on univariate settings (where all vertices have the same activity), this paper handles non-uniform complex parameters.
- Error Sensitivity Parameter: The authors introduce a novel "error sensitivity parameter" ($\beta$) to track how errors propagate through the recursion. This allows for a direct amortization argument to control errors even when vertex activities are not uniform.
- Rounding for LLL: To apply their results to the LLL, the authors develop a "rounding" algorithm. It starts with a fractional solution (probabilities) and iteratively fixes variables to 0 or 1 while ensuring the system stays within the Shearer region.
- Hardness Reductions: They use reductions from counting perfect matchings in regular bipartite graphs to prove #P-hardness for exact evaluation and membership testing.
Datasets
As a theoretical computer science paper, no empirical datasets were used. The results are proven for general graphs $G$ with maximum degree $d$ or bounded connective constants.
Key Insights and Ideas
- The "Slack" Matters: The running time depends heavily on the "slack" $\alpha$—the distance of the input vector from the boundary of the Shearer region. The authors found that the dependence on $1/\alpha$ in the exponent is $1/\sqrt{\alpha}$, which they prove is optimal for correlation-decay-based methods.
- Phase Transition in Complexity: The paper shows a beautiful alignment between physics and CS: the point where the polynomial starts having roots (a phase transition in physics) is exactly where the problem of approximating it becomes NP-hard.
- A New Path to LLL: Traditionally, the LLL is solved via "resampling" (Moser-Tardos). This paper provides a completely different approach based on polynomial evaluation and rounding, viewing the independence polynomial as a "pessimistic estimator" for the probability of avoiding bad events.
Key Results
- Deterministic FPTAS: For an $n$-vertex graph with max degree $d$, if the activities have slack $\alpha$, $Z(\mathbf{z})$ can be $(1+\epsilon)$-approximated in $(n/\alpha)^{O(\log(d)/\sqrt{\alpha})}$ time.
- Sub-exponential LLL Algorithm: They provide a deterministic algorithm for the LLL in the "variable model" that runs in sub-exponential time.
- Membership Testing: They provide an algorithm to test if a vector of probabilities is in the Shearer region within a multiplicative error of $1+\alpha$ in $(n/\alpha)^{O(\sqrt{n/\alpha} \log d)}$ time.
- Hardness: They prove that exactly evaluating the polynomial at a point in the Shearer region is #P-hard, as is testing exact membership in the region.
Limitations and Future Work
- Sub-exponential vs. Polynomial: While the algorithm is an FPTAS for fixed slack, the dependence on $1/\alpha$ leads to sub-exponential time in applications like the LLL where $\alpha$ might be $O(1/n)$. A major open question is whether a truly polynomial-time algorithm exists for these cases.
- The Gibbs Distribution Gap: In the positive activity setting, Markov Chain Monte Carlo (MCMC) methods are very effective because they can sample from the Gibbs distribution. No natural analogue of the Gibbs distribution exists for negative activities, leaving a gap that MCMC currently cannot fill.
- Connective Constant: While the paper extends results to graphs with bounded connective constants, the constants involved in the runtime are currently quite large.
Summary updated