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

DOI10.1145/3147211zbMath1451.68132arXiv1509.06430WikidataQ124849807 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 lemma; resampling algorithm; Shearer's criterion

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

60C05: Combinatorial probability

68W10: Parallel algorithms in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms