An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles

DOI10.1137/18M1167176zbMath1433.68603arXiv1504.02044WikidataQ124816724 ScholiaQ124816724MaRDI QIDQ4960448

Nicholas J. A. Harvey, Jan Vondrák

Publication date: 16 April 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.02044

zbMATH Keywords

randomized algorithmsLovász local lemmageneral probability spacespackings of rainbow spanning treesresampling oracles

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (6)

Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ Abstract polymer gas: a simple inductive proof of the Fernández-Procacci criterion ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Dynamic Sampling from Graphical Models

Cites Work

• Unnamed Item
• Unnamed Item
• On the facial Thue choice number of plane graphs via entropy compression method
• Edge-disjoint rainbow spanning trees in complete graphs
• Improved bounds on coloring of graphs
• Acyclic edge coloring through the Lovász local lemma
• Nonrepetitive colouring via entropy compression
• Linearly many rainbow trees in properly edge-coloured complete graphs
• Lopsided Lovász Local lemma and Latin transversals
• On a problem of Spencer
• Asymptotic lower bounds for Ramsey functions
• On the complexity of the parity argument and other inefficient proofs of existence
• Rainbow spanning trees in properly coloured complete graphs
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• The local cut lemma
• Acyclic edge-coloring using entropy compression
• Cluster expansion for abstract polymer models. New bounds from an old approach
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Quest for Negative Dependency Graphs
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• On the Facial Thue Choice Index via Entropy Compression
• Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion
• An Improvement of the Lovász Local Lemma via Cluster Expansion
• A Sharper Local Lemma with Improved Applications
• Random Walks That Find Perfect Objects and the Lovász Local Lemma
• An Extension of the Moser--Tardos Algorithmic Local Lemma
• A constructive proof of the general lovász local lemma
• Focused Stochastic Local Search and the Lovász Local Lemma
• Rainbow spanning trees in complete graphs colored by one‐factorizations
• An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles
• A constructive proof of the Lovász local lemma
• Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma
• A constructive algorithm for the Lovász Local Lemma on permutations
• New Constructive Aspects of the Lovász Local Lemma
• Rainbow Perfect Matchings in Complete Bipartite Graphs: Existence and Counting
• Deterministic Algorithms for the Lovász Local Lemma
• Moser and tardos meet Lovász
• Multicolored trees in complete graphs
• Multicolored trees in complete graphs
• Distributed algorithms for the Lovász local lemma and graph coloring

This page was built for publication: An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles