Improved algorithmic versions of the Lovász Local Lemma

TitleImproved algorithmic versions of the Lovász Local Lemma
Publication TypeConference Papers
Year of Publication2008
AuthorsSrinivasan A
Conference NameProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
Date Published2008///
PublisherSociety for Industrial and Applied Mathematics
Conference LocationPhiladelphia, PA, USA

The Lovász Local Lemma is a powerful tool in combinatorics and computer science. The original version of the lemma was nonconstructive, and efficient algorithmic versions have been developed by Beck, Alon, Molloy & Reed, et al. In particular, the work of Molloy & Reed lets us automatically extract efficient versions of essentially any application of the symmetric version of the Local Lemma. However, with some exceptions, there is a significant gap between what one can prove using the original Lemma nonconstructively, and what is possible through these efficient versions; also, some of these algorithmic versions run in super-polynomial time. Here, we lessen this gap, and improve the running time of all these applications (which cover all applications in the Molloy & Reed framework) to polynomial. We also improve upon the parallel algorithmic version of the Local Lemma for hypergraph coloring due to Alon, by allowing noticeably more overlap among the edges.