Commutative algorithms approximate the LLL-distribution

DOI10.4230/LIPICS.APPROX-RANDOM.2018.44MaRDI QIDQ5009540zbMATH OpenFDO

Authors Fotis Iliopoulos

Publication date 4 August 2021

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

zbMATH Keywords

coloring triangle-free graphscommutativityLLL-distributionlocal searchlovasz local lemma

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Commutativity in the Algorithmic Lovász Local Lemma
• New constructive aspects of the Lovász local lemma
• Distributed algorithms for the Lovász local lemma and graph coloring

Cites work

• A constructive algorithm for the Lovász local lemma on permutations
• A constructive proof of the general Lovász local lemma
• A constructive proof of the Lovász local lemma
• A parallel algorithmic version of the local lemma
• A sharper local lemma with improved applications
• An algorithmic approach to the Lovász local lemma. I
• An algorithmic proof of the Lovász local lemma via resampling oracles
• An extension of the Moser-Tardos algorithmic local lemma
• An improvement of the Lovász local lemma via cluster expansion
• Commutativity in the Algorithmic Lovász Local Lemma
• Deterministic algorithms for the Lovász local lemma
• Distributed algorithms for the Lovász local lemma and graph coloring
• Focused stochastic local search and the Lovász local lemma
• scientific article; zbMATH DE number 5764785 (Why is no real title available?)
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• scientific article; zbMATH DE number 1445282 (Why is no real title available?)
• Lopsidependency in the Moser-Tardos framework: beyond the lopsided Lovász local lemma
• Moser and tardos meet Lovász
• New constructive aspects of the Lovász local lemma
• Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma
• On a problem of Spencer
• Random walks that find perfect objects and the Lovász local lemma
• The Johansson-Molloy theorem for DP-coloring
• The list chromatic number of graphs with small clique number
• The Moser--Tardos Framework with Partial Resampling
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Using Lovász local lemma in the space of random injections

Cited in

(7)

• New bounds for the Moser-Tardos distribution
• Counting colorings of triangle-free graphs
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Commutative Algorithms Approximate the LLL-distribution
• Fundamentals of partial rejection sampling
• A new notion of commutativity for the algorithmic Lovász local lemma
• Variable version Lovász local lemma: a tale of two boundaries

This page was built for publication: Commutative algorithms approximate the LLL-distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009540)