English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study an algorithm for approximating the multivariate independencepolynomial $Z(\mathbf{z})$, with negative and complex arguments, an object thathas strong connections to combinatorics and to statistical physics. Inparticular, the independence polynomial with negative arguments,$Z(-\mathbf{p})$, determines the Shearer region, the maximal region ofprobabilities to which the Lovasz Local Lemma (LLL) can be extended (Shearer1985). In statistical physics, complex zeros of the independence polynomialrelate to existence of phase transitions.  Our main result is a deterministic algorithm to compute approximately theindependence polynomial in any root-free complex polydisc centered at theorigin. Our algorithm is essentially the same as Weitz's algorithm for positiveparameters up to the tree uniqueness threshold, and the core of our analysis isa novel multivariate form of the correlation decay technique, which can handlenon-uniform complex parameters. In particular, in the univariate real settingour work implies that Weitz's algorithm works in an interval between twocritical points $(\lambda'_c(d), \lambda_c(d))$, and outside of this intervalan approximation of $Z(\mathbf{z})$ is known to be NP-hard.  As an application, we give a sub-exponential time algorithm for testingapproximate membership in the Shearer region. We also give a new rounding baseddeterministic algorithm for Shearer's lemma (an extension of the LLL), which,however, runs in sub-exponential time. On the hardness side, we prove thatevaluating $Z(\mathbf{z})$ at an arbitrary point in Shearer's region, andtesting membership in Shearer's region, are #P-hard problems. We also establishthe best possible dependence of the exponent of the run time of Weitz'scorrelation decay technique in the negative regime on the distance to theboundary of the Shearer region.

Computing the Independence Polynomial: from the Tree Threshold down to the Roots