  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.
