Recent Progress on the Lovasz Local Lemma

Monday, March 16, 2015 - 4:00pm - 4:40pm
Klaus 2443
Aravind Srinivasan (University of Maryland)
Since the breakthroughs of Moser and Moser-Tardos, there has been steady progress on further algorithmic aspects of the Local Lemma; a key theme that has emerged is that Moser-Tardos is a random process of independent interest that is more than an algorithmic version of the Local Lemma. I will survey some of these developments, with an emphasis more on results than on proofs, although a basic proof-framework will be presented.