TY - CONF T1 - Improved algorithmic versions of the Lovász Local Lemma T2 - Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms Y1 - 2008 A1 - Srinivasan, Aravind AB - 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. JA - Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms T3 - SODA '08 PB - Society for Industrial and Applied Mathematics CY - Philadelphia, PA, USA UR - http://dl.acm.org/citation.cfm?id=1347082.1347150 ER -