@article{21143,
  abstract     = {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.},
  author       = {Harris, David G. and Iliopoulos, Fotios and Kolmogorov, Vladimir},
  issn         = {1557-2862},
  journal      = {Theory of Computing},
  number       = {5},
  pages        = {1 -- 34},
  publisher    = {University of Chicago Press},
  title        = {{A new notion of commutativity for the algorithmic Lovász Local Lemma}},
  doi          = {10.4086/toc.2025.v021a005},
  volume       = {21},
  year         = {2025},
}