Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, February 10, 2009, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Robin Moser

A Constructive Proof of the Lovász Local Lemma

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login