New Constructive Aspects of the Lovász Local Lemma

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.

Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: