Title: Moser and Tardos meet Lovasz
Speaker: Mario Szegedy, Rutgers University
Date: Tuesday, March 29, 2011 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Beck's early work gave an Efficient Version of the of the Lovasz Local Lemma(LLL), but with significant compromise in the parameters. Following several improvements (alon91,molloy98,czumaj00,srinivasan08), Moser, and Moser and Tardos obtained asymptotically optimal results in terms of the maximal degree. For a fixed dependency graph G, the exact criterion under which LLL applies, is given by Shearer. We show that: - For the variable version (i.e. in the Moser-Tardos setting), whenever the probabilities are 1-epsilon factor within Shearer's bound, the Moser-Tardos algorithm runs in expected time at most n/epsilon. Also, the running time is polynomial not only in the number of events, but also in the number of variables. This extends a theorem of Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. - We give a Moser and Tardos type algorithm for the general (non-variable) version of LLL, and obtain a simplified proof of Shearer's strengthening of LLL. - We give a majorizing lemma that connects bounds on different graphs. - We show that the LLL bound for the (special case of the) variable version is sometimes larger than for the general version.