Commutativity in the Random Walk formulation of the Lovasz Local Lemma.
Vladimir Kolmogorov · arXiv (Cornell University) · 2015
Recently, Achlioptas and Iliopoulos [1] proposed a new Random Walk framework for finding objects that avoid bad features, or flaws. It extends the Moser-Tardos resampling algorithm [12] to more general discrete spaces. At each step the method picks a flaw present in the current state and resamples it. However, it is less flexible than the Moser-Tardos method since [1] requires a specific flaw selection rule, whereas [12] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new commutativity condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we observe that the bound in [1] on the expected runtime of the algorithm can be improved in some cases.