Archive for December, 2010

New Constructive Aspects of the Lovász Local Lemma

December 13, 2010

Lovász Local Lemma is a strong probabilistic tool mainly used to prove results about existence of certain discrete structures. Last year R. Moser and G. Tardos presented an algorithm to actually construct those discrete structures. Their proof was really elegant. However, their analysis don’t always provide a polynomial bound for the running time. The authors of this paper, presented in this FOCS, extend their work by showing that the Moser-Tardos algorithm can indeed be altered a bit to give efficient Monte Carlo algorithms in many cases. More info can be found in this post. I enjoyed reading the paper and talked about it in the CombOpt reading group last Tuesday. By the way, the FOCS’10 talks are available online and you can watch the original presentation.