Lovasz Local Lemma

Javad Ebrahimi

Sunday, July 9, 2017,   11:00 - 12:30
Sunday, July 9, 2017,   14:00 - 15:30
Sunday, July 9, 2017,   16:00 - 17:30

VENUE   Lecture Hall 2, Niavaran Bldg.


Many problems in probabilistic combinatorics can be formulated as the question of whether a randomly selected object in a given probability space falls outside a set of events (which we call "bad events"), with positive probability. When the events are pairwise independent, if the probability of each event is less than 1, then with positive probability, none of the events will occur. Unfortunately, in practice, the bad events are not always pairwise independent.
Lovasz Local Lemma (or LLL for short) asserts that if the bad events satisfy some weaker form of independence condition, then there exists a constant number $p$, independent of the number of the events, for which the following holds. If the probability of each bad event is less than $p$, then there exists a positive (although typically exponentially small) lower bound on the probability that none of them occur. Consequently, random sampling algorithm may take exponential time before it hits an object outside all the bad events.
In this short-course, we first motivate, explain by several examples and prove LLL. Then, we present the breakthrough work of Moser and Tardos about an algorithmic version of LLL which runs in polynomial time, in expectation.