Theory of Computing
-------------------
Title     : A New Notion of Commutativity  for the Algorithmic Lovász Local Lemma
Authors   : David G. Harris, Fotios Iliopoulos, and Vladimir Kolmogorov
Volume    : 21
Number    : 5
Pages     : 1-34
URL       : https://theoryofcomputing.org/articles/v021a005

Abstract
--------

The Lovasz 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.