Title: Connecting three Local Lemmas
Speaker: Wes Pegden, NYU
Date: Tuesday, February 1, 2011 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Three recent results on the Local Lemma include a Lefthanded version which allows a 'one-sided' view of dependencies, a result of Bissacot, et al. improving the Lov'asz Local Lemma by giving a better approximation to an old characterization of Shearer by using techniques from the cluster expansion in statistical mechanics, and the recent breakthrough of Moser and Tardos, which gives an algorithmic version of the Local Lemma which is nearly as general as the standard Lov'asz Local Lemma. In this talk, we will discuss three new theorems connecting these independent versions of the Local Lemma.