Gábor TARDOS (Rényi Institute): An algorithmic version of the Lovász local lemma
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. |