Theory of Computing Seminar

Thursday January 28, 2016 12:00 PM

Properties and Generalizations of the Moser-Tardos Process

Speaker: Aravind Srinivasan, University of Maryland in QuICS
Location: Annenberg 213

Abstract:

Moser and Tardos have developed an elegant and powerful
algorithmic version of the Lovasz Local Lemma. Since the publication of
this work, it has become apparent that this algorithm has some very
interesting properties and extensions, and can be viewed as a stochastic
process of independent interest. I will survey some of these, especially
the ideas of "partial resampling" and the "LLL-distribution" (the
properties of the output distribution of Moser-Tardos).
 
I will draw from joint works with Haeupler and Saha, with Harris, and with Chen and Harris. 
Series Theory of Computing Seminar Series

Contact: Thomas Vidick vidick@cms.caltech.edu