Jochen Messner and Thomas Thierauf
Abstract:
Recently, Moser and Tardos came up with a
constructive proof of the Lovász Local Lemma.
In this paper,
we give another constructive proof of the lemma, based on Kolmogorov complexity.
Actually,
we even improve the Local Lemma slightly.