A Simple Algorithmic Proof of the Symmetric Lopsided Lovasz Local Lemma

摘要

We provide a simple algorithmic proof for the symmetric Lopsided Lovasz Local Lemma, a variant of the classic Lovasz Local Lemma, where, roughly, only the degree of the negatively correlated undesirable events counts. Our analysis refers to the algorithm by Moser (2009), however it is based on a simple application of the probabilistic method, rather than a counting argument, as are most of the analyses of algorithms for variants of the Lovasz Local Lemma.