Improved Algorithmic Versions of the Lovász Local Lemma
Aravind Srinivasan · 2008
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. 1