---
OA_place: publisher
OA_type: diamond
PlanS_conform: '1'
_id: '21143'
abstract:
- lang: eng
  text: "The Lovász Local Lemma (LLL) is a powerful tool in probabilistic\r\ncombinatorics
    which can be used to establish the existence of objects with certain\r\nproperties.
    The breakthrough paper by Moser & Tardos (STOC’09 and JACM 2010)\r\nand follow-up
    work revealed that the LLL has intimate connections with a class of\r\nstochastic
    local search algorithms for finding such desirable objects.\r\nBesides conditions
    for convergence, many other natural questions can be asked\r\nabout algorithms;
    for instance, “are they parallelizable?”, “how many solutions can\r\nthey output?”,
    “what is the expected ‘weight’ of a solution?”. These questions and\r\nmore have
    been answered for a class of LLL-inspired algorithms called commutative. In\r\nthis
    paper we introduce a new, very natural and more general notion of commutativity\r\n(essentially
    matrix commutativity) which allows us to show a number of new refined\r\nproperties
    of LLL-inspired local search algorithms with significantly simpler proofs."
acknowledgement: "This material is based on work directly supported by the IAS Fund
  for Math and indirectly supported by the National Science Foundation Grant No. CCF-1900460.
  Any opinions, findings and conclusions or recommendations expressed in this material
  are those of the author(s) and do not necessarily reflect the views of the National
  Science Foundation. This work is also supported by the National Science Foundation
  Grant No. CCF-1815328. Supported by the European Research Council under the European
  Union’s Seventh Framework Programme\r\n(FP7/2007-2013)/ERC grant agreement no 616160."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: David G.
  full_name: Harris, David G.
  last_name: Harris
- first_name: Fotios
  full_name: Iliopoulos, Fotios
  last_name: Iliopoulos
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: 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>
  apa: 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>
  chicago: 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>.
  ieee: 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.
  ista: 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.
  mla: 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>.
  short: D.G. Harris, F. Iliopoulos, V. Kolmogorov, Theory of Computing 21 (2025)
    1–34.
corr_author: '1'
date_created: 2026-02-05T12:04:58Z
date_published: 2025-09-08T00:00:00Z
date_updated: 2026-02-10T10:00:00Z
day: '08'
ddc:
- '510'
department:
- _id: VlKo
doi: 10.4086/toc.2025.v021a005
ec_funded: 1
external_id:
  arxiv:
  - '2008.05569'
file:
- access_level: open_access
  checksum: 5a9f7cfccac6046fe75a14a4059eed04
  content_type: application/pdf
  creator: dernst
  date_created: 2026-02-10T09:54:28Z
  date_updated: 2026-02-10T09:54:28Z
  file_id: '21209'
  file_name: 2025_TheoryComputing_Harris.pdf
  file_size: 509346
  relation: main_file
  success: 1
file_date_updated: 2026-02-10T09:54:28Z
has_accepted_license: '1'
intvolume: '        21'
issue: '5'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 1 - 34
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Theory of Computing
publication_identifier:
  eissn:
  - 1557-2862
publication_status: published
publisher: University of Chicago Press
quality_controlled: '1'
related_material:
  record:
  - id: '10072'
    relation: earlier_version
    status: public
status: public
title: A new notion of commutativity for the algorithmic Lovász Local Lemma
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2025'
...