CSEDays. Theory 2013

Ural Federal University, Ekaterinburg, Russia, June 29 - July 01

News subscription
Share:

Reviews

В этом году были великолепные лекторы — даже просто тот факт, что на школу приехал профессор из Великобритании, это уже выдающееся достижение. Причем, Георгий Ржевский и Петр Скобелев хорошо дополняли друг друга. Осознал, что нам в УрГУ не хватает людей такого уровня. Профессоры, которые уже многого достигли в своей жизни и до сих пор в здравом уме и с искрой в глазах. Смотришь на таких людей и заражаешься их энтузиазмом и энергией.
Борис / CSEDays. Application 2011
Home / Mario Szegedy /

Lovasz Local Lemma

Author: Mario Szegedy

Lovasz in the early seventies invented his celebrated local lemma (LLL) to prove the existence of combinatorial objects that satisfy a prescribed sparse set of constraints. His beautiful proof was inherently non-constructive. Nearly two decades later J. Beck presented a constructive proof, which was however seen as technical.

In 2008 Robin A. Moser and in 2009 Moser and Gabor Tardos turned the LLL research around by giving a constructive proof with a simple resample process (algorithm) at its heart.

We describe the original proof of Lovasz and the new proof Moser and Tardos. Then we discuss a great number of consequences of the original and new results.