Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 10, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Robin Moser
The Lovász Local Lemma [Erdős, Lovász, 1975] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Beck, 1991], Beck demonstrated that a constructive variant can be given under certain more restrictive conditions. Simplifications of his procedure and relaxations of its restrictions were subsequently exhibited in several publications [Alon; Molloy and Reed; Czumaj, Scheideler; Srinivasan; M].
In this talk, a new algorithm is presented that can find the object guaranteed to exist by the Local Lemma in polynomial time. In contrast to all previous approaches, the new algorithm applies to almost all known applications of the lemma and since the original non-constructive proofs are not invoked anymore, it can be regarded as a constructive proof variant.
Joint work with Gábor Tardos.
Automatic MiSe System Software Version 1.4803M | admin login