An algorithmic version of the Lovász local lemma

Date:

Thursday, December 18, 2014 - 4:15pm

Gábor TARDOS (Rényi Institute): An algorithmic version of the Lovász local lemma

The probabilistic method is an efficient way to prove the existence of certain combinatorial structures when constructions are not available (or harder to get). For this we define a discrete probability space on the structures and prove the the desired property holds with positive probability. For a long while the method mostly worked if the

probability was not only positive but overwhelming (close to 1). While effectively and deterministically find such a structure may still be hard, a randomized algorithm is trivial: just pick a random sample from the space and check if the desired property holds. The Lovász local lemma (1975) gave a tool to prove the probability of a property is positive in many cases even if the probability itself was exponentially small. In these cases finding the desired structure (a needle in the haystack) is challenging even for a randomized algorithm. We show that a very simple and intuitive randomized algorithm does exactly that: it quickly finds a desired structure.

Most of the talk is based on a 2010 joint paper with Robin Moser with pointers for more recent developments if time permits.

When	Thu Dec 18, 2014 4:15pm – 5:15pm Budapest
Where	Budapesti Műszaki Egyetem, H épület, III. emelet 306.