Moser-Tardos Algorithm: Beyond Shearer's Bound
Moser-Tardos Algorithm: Beyond Shearer's Bound
In a seminal paper (Moser and Tardos, JACM'10), Moser and Tardos developed a simple and powerful algorithm to find solutions to combinatorial problems in the variable Lov{\'a}sz Local Lemma (LLL) setting. Kolipaka and Szegedy (STOC'11) proved that the Moser-Tardos algorithm is efficient up to the tight condition of the abstract …