Title: A Sharper Local Lemma with Improved Applications
Speaker: Mario Szegedy, Rutgers University
Date: Wednesday, February 22, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We give a new family of Lovasz Local Lemmas (LLL), with applications. Shearer has given the most general condition under which the Lovasz Local Lemma (LLL) holds, but the original condition of Lovasz is simpler and more practical. As far as we know, apart from, this is the only other version that lies between the original LLL and Shearer's bounds. Moser-Tardos (MT) have made the (original) LLL efficient, and later their algorithm was shown to work up to Shearer's bound. Do we have to make a choice between practical and optimal? In this article we present a continuum of LLL bounds between the original and Shearer's bounds. One of these, which we call Clique LLL (CLLL), particularly stands out, and is natural in those settings, where the event space is defined with independent random variables (\'a la MT). Using this version we get improved bounds in applications for Acyclic Edge Coloring and Non-repetitive Vertex Coloring. The running time of the Resample algorithm of MT for Clique LLL also has a convenient expression.
Joint work with Kashyap Kolipaka, Yixin Xu