Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs

DOI10.1145/3147211zbMath1451.68132arXiv1509.06430OpenAlexW2772781679WikidataQ124849807 ScholiaQ124849807MaRDI QIDQ4554943

Bernhard Haeupler, David G. Harris

Publication date: 12 November 2018

Published in: ACM Transactions on Algorithms, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Lovász local lemmaresampling algorithmShearer's criterion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items

Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel, Unnamed Item, New bounds for the Moser‐Tardos distribution, A Time Hierarchy Theorem for the LOCAL Model