2016/08/07 by Nicholas J. A. Harvey, Harvey, Nicholas J. A., Piyush Srivastava +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1608.02282
openalex publication_date 2016/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study an algorithm for approximating the multivariate independence\npolynomial Z(\z), with negative and complex arguments, an object that\nhas strong connections to combinatorics and to statistical physics. In\nparticular, the independence polynomial with negative arguments,\nZ(-\p), determines the Shearer region, the maximal region of\nprobabilities to which the Lovasz Local Lemma (LLL) can be extended (Shearer\n1985). In statistical physics, complex zeros of the independence polynomial\nrelate to existence of phase transitions.\n Our main result is a deterministic algorithm to compute approximately the\nindependence polynomial in any root-free complex polydisc centered at the\norigin. Our algorithm is essentially the same as Weitz's algorithm for positive\nparameters up to the tree uniqueness threshold, and the core of our analysis is\na novel multivariate form of the correlation decay technique, which can handle\nnon-uniform complex parameters. In particular, in the univariate real setting\nour work implies that Weitz's algorithm works in an interval between two\ncritical points (\λ'c(d), \λc(d)), and outside of this interval\nan approximation of Z(\z) is known to be NP-hard.\n As an application, we give a sub-exponential time algorithm for testing\napproximate membership in the Shearer region. We also give a new rounding based\ndeterministic algorithm for Shearer's lemma (an extension of the LLL), which,\nhowever, runs in sub-exponential time. On the hardness side, we prove that\nevaluating Z(\z) at an arbitrary point in Shearer's region, and\ntesting membership in Shearer's region, are #P-hard problems. We also establish\nthe best possible dependence of the exponent of the run time of Weitz's\ncorrelation decay technique in the negative regime on the distance to the\nboundary of the Shearer region.\n