%0 Conference Paper
%B Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
%D 2008
%T Improved algorithmic versions of the Lovász Local Lemma
%A Srinivasan, Aravind
%X 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.
%B Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
%S SODA '08
%I Society for Industrial and Applied Mathematics
%C Philadelphia, PA, USA
%P 611 - 620
%8 2008///
%G eng
%U http://dl.acm.org/citation.cfm?id=1347082.1347150