A constructive proof of the Lovász local lemma

From MaRDI portal
Publication:5172728

DOI10.1145/1536414.1536462zbMath1304.68079arXiv0810.4812OpenAlexW2019883273MaRDI QIDQ5172728

Robin A. Moser

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




Related Items (34)

The list chromatic number of graphs with small clique numberGraph theory -- a survey on the occasion of the Abel Prize for László LovászRainbow Hamilton cycles and lopsidependencyProbabilistic existence of regular combinatorial structuresDisproof of the neighborhood conjecture with implications to SATA Short Implicant of a CNF Formula with Many Satisfying AssignmentsEfficiently list‐edge coloring multigraphs asymptotically optimallyTotal functions in QMAProbabilistic existence of large sets of designsA new bound on the acyclic edge chromatic numberOn triangle-free list assignmentsInteractions of computational complexity theory and mathematicsMini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022Unnamed ItemAcyclic edge-coloring using entropy compressionColouring graphs when the number of colours is almost the maximum degreeCertifying algorithmsAsymptotic and constructive methods for covering perfect hash families and covering arraysAcyclic edge coloring through the Lovász local lemmaA Kolmogorov complexity proof of the Lovász local lemma for satisfiabilityAsymptotically optimal frugal colouringEntropy compression versus Lovász local lemmaSemidefinite optimization in discrepancy theoryGrasshopper avoidance of patternsA short implicant of a CNF formula with many satisfying assignmentsStar-factors in graphs with large minimum degreeAn Algorithmic Proof of the Lovász Local Lemma via Resampling OraclesDirected Lovász local lemma and Shearer's lemmaWitness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gasLocal embeddings of metric spacesDistributed algorithms for the Lovász local lemma and graph coloringFinding independent transversals efficientlyA Local Lemma for Focused Stochastic AlgorithmsUpper Bounds on the Size of Covering Arrays




This page was built for publication: A constructive proof of the Lovász local lemma