article published yes Vladimir Kolmogorov author 3D50B0BA-F248-11E8-B48F-1D18A9856A87 VlKo department Discrete Optimization in Computer Vision: Theory and Practice project We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Har-vey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad features,” or “flaws.” It extends the Moser–Tardos resampling algorithm [R. A. Moser andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces. At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw). However, the recent formu-lation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently). We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additionalassumption. We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition. Society for Industrial and Applied Mathematics2018 eng 0097-5397 1095-7111 1506.08547 00045378510000110.1137/16m1093306 4762029-2056 https://research-explorer.ista.ac.at/record/1193 V. Kolmogorov, “Commutativity in the algorithmic Lovász local lemma,” <i>SIAM Journal on Computing</i>, vol. 47, no. 6. Society for Industrial and Applied Mathematics, pp. 2029–2056, 2018. Kolmogorov V. 2018. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 47(6), 2029–2056. Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” <i>SIAM Journal on Computing</i>, vol. 47, no. 6, Society for Industrial and Applied Mathematics, 2018, pp. 2029–56, doi:<a href="https://doi.org/10.1137/16m1093306">10.1137/16m1093306</a>. Kolmogorov, V. (2018). Commutativity in the algorithmic Lovász local lemma. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/16m1093306">https://doi.org/10.1137/16m1093306</a> Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2018. <a href="https://doi.org/10.1137/16m1093306">https://doi.org/10.1137/16m1093306</a>. Kolmogorov V. Commutativity in the algorithmic Lovász local lemma. <i>SIAM Journal on Computing</i>. 2018;47(6):2029-2056. doi:<a href="https://doi.org/10.1137/16m1093306">10.1137/16m1093306</a> V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056. 59752019-02-13T12:59:33Z2025-09-22T09:44:20Z