Theory of Computing Seminar
Annenberg 213
Properties and Generalizations of the Moser-Tardos Process
Aravind Srinivasan,
University of Maryland in QuICS,
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).
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.
For more information, please contact Thomas Vidick by email at [email protected].
Event Series
Theory of Computing Seminar Series