Extensions of the Algorithmic Lovasz Local Lemma
share
We consider recent formulations of the algorithmic Lovasz Local Lemma by Achlioptas-Iliopoulos-Kolmogorov [2] and by Achlioptas-Iliopoulos-Sinclair [3]. These papers analyze a random walk algorithm for finding objects that avoid undesired "bad events" (or "flaws"), and prove that under certain conditions the algorithm is guaranteed to find a "flawless" object quickly. We show that conditions proposed in these papers are incomparable, and introduce a new family of conditions that includes those in [2, 3] as special cases. Secondly, we extend our previous notion of "commutativity" in [15] to this more general setting, and prove that it allows to use an arbitrary strategy for selecting the next flaw to address. In the special case of primary flaws we prove a stronger property: the flaw selection strategy does not affect at all the expected number of steps until termination, and also does not affect the distribution induced by the algorithm upon termination. This applies, in particular, to the single-clause backtracking algorithm for constraint satisfaction problems considered in [3].
READ FULL TEXT