@conference {17601,
	title = {Improved algorithmic versions of the Lov{\'a}sz Local Lemma},
	booktitle = {Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms},
	series = {SODA {\textquoteright}08},
	year = {2008},
	month = {2008///},
	pages = {611 - 620},
	publisher = {Society for Industrial and Applied Mathematics},
	organization = {Society for Industrial and Applied Mathematics},
	address = {Philadelphia, PA, USA},
	abstract = {The Lov{\'a}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.},
	url = {http://dl.acm.org/citation.cfm?id=1347082.1347150},
	author = {Srinivasan, Aravind}
}
