Seminar

Lovasz\\'s Local Lemma (LLL) finds a wide variety of applications in combinatorics and computer science. It allows to deduce the existence of a global solution for any system of constraints, whose variable set has intersection graph G, as long as the probability that any given constraint is not satisfied is below a threshold that depends only on the maximal degree of G. Beck has turned Lovasz\\'s existence proof into an algorithm, but with a weaker dependence on the max degree.

Following several improvements Moser, and Moser and Tardos have developed a very simple algorithm, which is also optimal, when the degree tends to infinity. Their analysis reaches a certain natural bound (in terms of the entire G) with which the lemma was stated in the original paper of Lovasz.

In the lemma, as stated by Lovasz, the events are not necessarily defined via an intersection graph for a family of constraints, but rather by a graph G that describes dependencies. For a fixed dependency graph G, the exact criterion under which the general LLL applies, is given by Shearer. We show that the analysis of the MT algorithm can be improved all the way to Shearer\\'s bound. In particular, whenever the probabilities are 1-epsilon factor within Shearer\\'s bound, the Moser-Tardos algorithm runs in expected time at most n /epsilon. This makes the efficient version an exact match to the non-efficient one.

We also give a deeper reason for this co-incidence: A variant of the Moser-Tardos argument can actually prove the general LLL.

Finally, we show that variable framework represents a real restriction. The LLL bound for the variable version for some G is higher than for the general version. This, of course, raises the question if the MT algorithm can efficiently achieve this higher bound.

Joint work with Kashyap Kolipaka