Lopsidependency in the Moser-Tardos Framework

DOI10.1145/3015762zbMath1446.68108OpenAlexW2198255326WikidataQ124817994 ScholiaQ124817994MaRDI QIDQ4962634

David G. Harris

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey numberHamiltonian cycleLovász local lemmaindependent transversalslopsided Lovász local lemmaMoser-Tardos algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Combinatorial probability (60C05) Parallel algorithms in computer science (68W10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (8)

Rainbow Hamilton cycles and lopsidependency ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ 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 ⋮ Finding independent transversals efficiently ⋮ Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma

This page was built for publication: Lopsidependency in the Moser-Tardos Framework