A constructive proof of the Lovász local lemma
From MaRDI portal
Publication:5172728
DOI10.1145/1536414.1536462zbMath1304.68079arXiv0810.4812OpenAlexW2019883273MaRDI QIDQ5172728
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0810.4812
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (34)
The list chromatic number of graphs with small clique number ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ Rainbow Hamilton cycles and lopsidependency ⋮ Probabilistic existence of regular combinatorial structures ⋮ Disproof of the neighborhood conjecture with implications to SAT ⋮ A Short Implicant of a CNF Formula with Many Satisfying Assignments ⋮ Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ Total functions in QMA ⋮ Probabilistic existence of large sets of designs ⋮ A new bound on the acyclic edge chromatic number ⋮ On triangle-free list assignments ⋮ Interactions of computational complexity theory and mathematics ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ Unnamed Item ⋮ Acyclic edge-coloring using entropy compression ⋮ Colouring graphs when the number of colours is almost the maximum degree ⋮ Certifying algorithms ⋮ Asymptotic and constructive methods for covering perfect hash families and covering arrays ⋮ Acyclic edge coloring through the Lovász local lemma ⋮ A Kolmogorov complexity proof of the Lovász local lemma for satisfiability ⋮ Asymptotically optimal frugal colouring ⋮ Entropy compression versus Lovász local lemma ⋮ Semidefinite optimization in discrepancy theory ⋮ Grasshopper avoidance of patterns ⋮ A short implicant of a CNF formula with many satisfying assignments ⋮ Star-factors in graphs with large minimum degree ⋮ 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 ⋮ Local embeddings of metric spaces ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Finding independent transversals efficiently ⋮ A Local Lemma for Focused Stochastic Algorithms ⋮ Upper Bounds on the Size of Covering Arrays
This page was built for publication: A constructive proof of the Lovász local lemma
