Weitz's Algorithm and the Lovasz Local Lemma

The work of Shearer, and of Scott and Sokal, established important connections between the study of the independence polynomial evaluated at negative activities and the Lovasz local lemma. In particular, it is known that the zero free region (known as the "Shearer region") of the independence polynomial around the origin determines the optimal region of applicability for certain forms of the Lovasz local lemma. 

 

Recent results (of Patel and Regts, Galanis, Goldberg and Stefankovic, and of an earlier version of this work) have shown that the Shearer region also defines a "complexity-theoretic" phase transition analogous to the one on the positive activity side established by the results of Weitz and Sly: in particular, evaluating the independence polynomial admits an FPTAS in the Shearer region, but becomes NP-hard outside it. 

 

In this work, we perform an optimal analysis of an adaption of Weitz's correlation decay method inside the Shearer region that allows us to produce a much finer picture of the above transition on the algorithmic side. With this improved analysis, we are also able to show non-trivial applications to problems related to the Lovasz Local lemma. In particular, we give a new sub-exponential time algorithm for testing membership in the Shearer region, and also give a new sub exponential time algorithmic version of the LLL using black box evaluations of the independence polynomial.

 

Joint work with Nicholas J. A. Harvey and Jan Vondrák.