%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