article published yes David G. Harris author Fotios Iliopoulos author Vladimir Kolmogorov author 3D50B0BA-F248-11E8-B48F-1D18A9856A87 VlKo department Discrete Optimization in Computer Vision: Theory and Practice project The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects with certain properties. The breakthrough paper by Moser & Tardos (STOC’09 and JACM 2010) and follow-up work revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. Besides conditions for convergence, many other natural questions can be asked about algorithms; for instance, “are they parallelizable?”, “how many solutions can they output?”, “what is the expected ‘weight’ of a solution?”. These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs. https://research-explorer.ista.ac.at/download/21143/21209/2025_TheoryComputing_Harris.pdf application/pdfno University of Chicago Press2025 eng 1557-2862 2008.0556910.4086/toc.2025.v021a005 2151 - 34 https://research-explorer.ista.ac.at/record/10072 D.G. Harris, F. Iliopoulos, V. Kolmogorov, Theory of Computing 21 (2025) 1–34. D. G. Harris, F. Iliopoulos, and V. Kolmogorov, “A new notion of commutativity for the algorithmic Lovász Local Lemma,” <i>Theory of Computing</i>, vol. 21, no. 5. University of Chicago Press, pp. 1–34, 2025. Harris DG, Iliopoulos F, Kolmogorov V. A new notion of commutativity for the algorithmic Lovász Local Lemma. <i>Theory of Computing</i>. 2025;21(5):1-34. doi:<a href="https://doi.org/10.4086/toc.2025.v021a005">10.4086/toc.2025.v021a005</a> Harris DG, Iliopoulos F, Kolmogorov V. 2025. A new notion of commutativity for the algorithmic Lovász Local Lemma. Theory of Computing. 21(5), 1–34. Harris, David G., Fotios Iliopoulos, and Vladimir Kolmogorov. “A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.” <i>Theory of Computing</i>. University of Chicago Press, 2025. <a href="https://doi.org/10.4086/toc.2025.v021a005">https://doi.org/10.4086/toc.2025.v021a005</a>. Harris, David G., et al. “A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.” <i>Theory of Computing</i>, vol. 21, no. 5, University of Chicago Press, 2025, pp. 1–34, doi:<a href="https://doi.org/10.4086/toc.2025.v021a005">10.4086/toc.2025.v021a005</a>. Harris, D. G., Iliopoulos, F., &#38; Kolmogorov, V. (2025). A new notion of commutativity for the algorithmic Lovász Local Lemma. <i>Theory of Computing</i>. University of Chicago Press. <a href="https://doi.org/10.4086/toc.2025.v021a005">https://doi.org/10.4086/toc.2025.v021a005</a> 211432026-02-05T12:04:58Z2026-02-10T10:00:00Z