A new notion of commutativity for the algorithmic Lovász Local Lemma Harris, David G. Iliopoulos, Fotios Kolmogorov, Vladimir ddc:510 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. University of Chicago Press 2025 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/21143 https://research-explorer.ista.ac.at/download/21143/21209 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> eng info:eu-repo/semantics/altIdentifier/doi/10.4086/toc.2025.v021a005 info:eu-repo/semantics/altIdentifier/e-issn/1557-2862 info:eu-repo/semantics/altIdentifier/arxiv/2008.05569 https://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess