Commutativity in the Algorithmic Lovász Local Lemma

DOI10.1137/16M1093306zbMath1429.60018arXiv1506.08547WikidataQ124807702 ScholiaQ124807702MaRDI QIDQ4555400

Vladimir Kolmogorov

Publication date: 20 November 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.08547

zbMATH Keywords

Lovász local lemmaMoser-Tardos algorithm

Mathematics Subject Classification ID

Combinatorial probability (60C05) Extremal set theory (05D05)

Related Items (4)

Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ New bounds for the Moser‐Tardos distribution

Cites Work

• Unnamed Item
• Improved bounds on coloring of graphs
• Acyclic edge coloring through the Lovász local lemma
• Lopsided Lovász Local lemma and Latin transversals
• On a problem of Spencer
• Quest for Negative Dependency Graphs
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• An Improvement of the Lovász Local Lemma via Cluster Expansion
• An Extension of the Moser--Tardos Algorithmic Local Lemma
• A constructive proof of the general lovász local lemma
• Focused Stochastic Local Search and the Lovász Local Lemma
• The Lovász Local Lemma – A Survey
• A constructive algorithm for the Lovász Local Lemma on permutations
• Moser and tardos meet Lovász

This page was built for publication: Commutativity in the Algorithmic Lovász Local Lemma