Moser and tardos meet Lovász

DOI10.1145/1993636.1993669zbMath1288.68129OpenAlexW2066969286MaRDI QIDQ5419093

Kashyap Babu Rao Kolipaka

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993636.1993669

zbMATH Keywords

Lovász local lemmaindependent set polynomialhardcore lattice gasmatrix iterative analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

Commutativity in the Algorithmic Lovász Local Lemma ⋮ Rainbow Hamilton cycles and lopsidependency ⋮ Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ Unnamed Item ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ New bounds for the Moser‐Tardos distribution ⋮ A short proof of Bernoulli disjointness via the local lemma ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Nonrepetitive colouring via entropy compression ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Directed Lovász local lemma and Shearer's lemma ⋮ Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas ⋮ Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Finding independent transversals efficiently ⋮ Measurable versions of the Lovász local lemma and measurable graph colorings ⋮ Approximately counting bases of bicircular matroids ⋮ Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma

This page was built for publication: Moser and tardos meet Lovász