Revised: March 29, 2025
Published: September 8, 2025
Abstract: [Plain Text Version]
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.
---------------
A preliminary version of this paper appeared in the Proceedings of RANDOM 2021.
Licensed under a Creative Commons Attribution License (CC-BY)