The Lovasz Local Lemma establishes under certain assumptions that a collection of events can simultaneously fail to occur. The initial proofs from the 1970's used probabilistic techniques, hence were non-constructive. People worked on providing a constructive proof and had partial results based on substantially weaker assumptions about the relationship of the events. In 2008, Robin Moser greatly improved on these results, demonstrating an algorithm running in polynomial time that produces such an outcome for a standard case. With Gabor Tardos in 2009, he extended this result to recover every previously known application of the Local Lemma (though not quite the original statement).

The Lovasz Local Lemma establishes under certain assumptions that a collection of events can simultaneously fail to occur. The initial proofs from the 1970's used probabilistic techniques, hence were non-constructive. People worked on providing a constructive proof and had partial results based on substantially weaker assumptions about the relationship of the events. In 2008, Robin Moser greatly improved on these results, demonstrating an algorithm running in polynomial time that produces such an outcome for a standard case. With Gabor Tardos in 2009, he extended this result to recover every previously known application of the Local Lemma (though not quite the original statement).

The Lovasz Local Lemma establishes under certain assumptions that a collection of events can simultaneously fail to occur. The initial proofs from the 1970's were used the techniques of probabilistic techniques, hence were non-constructive. People worked on providing a constructive proof and had partial results based on substantially weaker assumptions about the relationship of the events. In 2008, Robin Moser greatly improved on these results, demonstrating an algorithm running in polynomial time that produces such an outcome for a standard case. With Gabor Tardos in 2009, he extended this result to recover every previously known application of the Local Lemma (though not quite the original statement).

The Lovasz Local Lemma establishes under certain assumptions that a collection of events can simultaneously fail to occur. The initial proofs from the 1970's used probabilistic techniques, hence were non-constructive. People worked on providing a constructive proof and had partial results based on substantially weaker assumptions about the relationship of the events. In 2008, Robin Moser greatly improved on these results, demonstrating an algorithm running in polynomial time that produces such an outcome for a standard case. With Gabor Tardos in 2009, he extended this result to recover every previously known application of the Local Lemma (though not quite the original statement).