A constructive proof of the general lovász local lemma
From MaRDI portal
Publication:3578191
DOI10.1145/1667053.1667060zbMath1300.60024arXiv0903.0544OpenAlexW2109693504WikidataQ124802019 ScholiaQ124802019MaRDI QIDQ3578191
Publication date: 14 July 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0903.0544
Nonnumerical algorithms (68W05) Combinatorial probability (60C05) Graph algorithms (graph-theoretic aspects) (05C85) Extremal combinatorics (05D99)
Related Items (only showing first 100 items - show all)
Unnamed Item ⋮ Counting colorings of triangle-free graphs ⋮ Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing ⋮ Detecting arrays for effects of single factors ⋮ Approaching repetition thresholds via local resampling and entropy compression ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Extremal bipartite independence number and balanced coloring ⋮ Measurable graph combinatorics ⋮ Inapproximability of counting independent sets in linear hypergraphs ⋮ On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing ⋮ Bounds and algorithms for generalized superimposed codes ⋮ Unnamed Item ⋮ Edge colorings avoiding patterns ⋮ On triangle-free list assignments ⋮ An extension of a construction of covering arrays ⋮ Distributed coloring of hypergraphs ⋮ Optimization in graphical small cancellation theory ⋮ Interactions of computational complexity theory and mathematics ⋮ Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters ⋮ Partitioning problems via random processes ⋮ Better trees for Santa Claus ⋮ A new kind of selectors and their applications to conflict resolution in wireless multichannels networks ⋮ Frameproof codes, separable codes and \(B_2\) codes: bounds and constructions ⋮ Fundamentals of partial rejection sampling ⋮ A note on the \(k\)-restriction problem ⋮ A survey of cover-free families: constructions, applications, and generalizations ⋮ An algorithmic construction of union-intersection-bounded families ⋮ Fast sampling of satisfying assignments from random \(k\)-SAT with applications to connectivity ⋮ An efficient algorithm for group testing with runlength constraints ⋮ Combinatorial constructions of separating codes ⋮ Non-constructive upper bounds for repetition thresholds ⋮ Local embeddings of metric spaces ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ A Local Lemma for Focused Stochastic Algorithms ⋮ O(log m)-approximation for the routing open shop problem ⋮ Hats, auctions and derandomization ⋮ Dynamic Sampling from Graphical Models ⋮ Upper Bounds on the Size of Covering Arrays ⋮ On a combinatorial framework for fault characterization ⋮ Algorithms for Constructing Anonymizing Arrays ⋮ \((1, j)\)-set problem in graphs ⋮ New bounds for the acyclic chromatic index ⋮ On Conflict-Free Multi-coloring ⋮ The list chromatic number of graphs with small clique number ⋮ A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ Commutativity in the Algorithmic Lovász Local Lemma ⋮ A note on near-optimal coloring of shift hypergraphs ⋮ On the Facial Thue Choice Index via Entropy Compression ⋮ Rainbow Hamilton cycles and lopsidependency ⋮ Probabilistic existence of regular combinatorial structures ⋮ Covering metric spaces by few trees ⋮ Counting Candy Crush configurations ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ DELAUNAY STABILITY VIA PERTURBATIONS ⋮ Improved upper bound for the degenerate and star chromatic numbers of graphs ⋮ A Short Implicant of a CNF Formula with Many Satisfying Assignments ⋮ A General Framework for Hypergraph Coloring ⋮ Bisecting and \(D\)-secting families for set systems ⋮ Bandwidth and low dimensional embedding ⋮ Counting Solutions to Random CNF Formulas ⋮ Edge-partitioning 3-edge-connected graphs into paths ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Acyclic coloring of graphs without bichromatic long path ⋮ What can be sampled locally? ⋮ Application of entropy compression in pattern avoidance ⋮ Improved bounds on coloring of graphs ⋮ Total functions in QMA ⋮ Probabilistic existence of large sets of designs ⋮ Another approach to non-repetitive colorings of graphs of bounded degree ⋮ Unnamed Item ⋮ A new bound on the acyclic edge chromatic number ⋮ Expander spanning subgraphs with large girth ⋮ On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ THE LOGARITHMICALLY AVERAGED CHOWLA AND ELLIOTT CONJECTURES FOR TWO-POINT CORRELATIONS ⋮ New bounds for the Moser‐Tardos distribution ⋮ Equivariant maps to subshifts whose points have small stabilizers ⋮ A rainbow blow‐up lemma ⋮ Acyclic edge-coloring using entropy compression ⋮ Colouring graphs when the number of colours is almost the maximum degree ⋮ Progress on the Adjacent Vertex Distinguishing Edge Coloring Conjecture ⋮ Colorful strips ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Generalized arboricity of graphs with large girth ⋮ A note on the discrepancy of matrices with bounded row and column sums ⋮ On weak odd domination and graph-based quantum secret sharing ⋮ Generating square-free words efficiently ⋮ Asymptotic and constructive methods for covering perfect hash families and covering arrays ⋮ The Lovász local lemma and variable strength covering arrays ⋮ Generalized acyclic edge colorings via entropy compression ⋮ Towards the linear arboricity conjecture ⋮ Pathwidth and nonrepetitive list coloring ⋮ Hölder-type inequalities and their applications to concentration and correlation bounds
This page was built for publication: A constructive proof of the general lovász local lemma
