A Constructive Proof of the Lovász Local Lemma by Robin Moser
The Lovász local lemma informally states that if you have a large set of events with limited dependence and they individually have a reasonable chance of happening, then there is a positive probability that they all happen. Moser focused on the special case of Boolean formula satisfiability: If we have a k-CNF formula φ where each clause shares a variable with at most r other clauses with r<2k/8 then φ is satisfiable. Note the result does not depend on the number of variables or clauses.
Moser gave this simple algorithm and a proof using entropy that I recognized as a Kolmogorov complexity argument and so excited me that I immediately wrote up the Kolmogorov proof as a blog post.
Moser's paper kickstarted a whole research agenda, with tight bounds using even simpler algorithms (though more complex proofs) and various generalizations. A whole tutorial day of STOC 2014 focused on the local lemma describing research that directly or indirectly came from Moser's most beautiful construction.
Moser gave this simple algorithm and a proof using entropy that I recognized as a Kolmogorov complexity argument and so excited me that I immediately wrote up the Kolmogorov proof as a blog post.
Moser's paper kickstarted a whole research agenda, with tight bounds using even simpler algorithms (though more complex proofs) and various generalizations. A whole tutorial day of STOC 2014 focused on the local lemma describing research that directly or indirectly came from Moser's most beautiful construction.
Will there be videos from this tutorial day?
ReplyDeleteCan someone summarize the tutorial talks in blog? Really, we need more informative blog posts from Computational Complexity, please.
ReplyDeleteGiven the significance of Moser's results on the LLL, it indeed seems to be a big a loss for our field that his LinkedIn profile suggests that he is no longer involved in basic research.
ReplyDelete