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
Abstract

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.

URLhttp://dl.acm.org/citation.cfm?id=1347082.1347150