Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
From MaRDI portal
Publication:6076732
DOI10.1002/rsa.21152arXiv1909.08065WikidataQ124800308 ScholiaQ124800308MaRDI QIDQ6076732
Publication date: 17 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.08065
Cites Work
- Deterministic parallel algorithms for bilinear objective functions
- Lopsided Lovász Local lemma and Latin transversals
- Extremal problems for transversals in graphs with bounded degree
- On a problem of Spencer
- A remark concerning arithmetic progressions
- Pseudorandom generators for space-bounded computation
- \(\text{RL}\subseteq \text{SC}\)
- A condition for matchability in hypergraphs
- Nonrepetitive graph colouring
- Independent systems of representatives in weighted graphs
- An Improvement of the Lovász Local Lemma via Cluster Expansion
- The Local Lemma Is Asymptotically Tight for SAT
- An improved bound for the strong chromatic number
- A constructive proof of the general lovász local lemma
- Algorithmic derandomization via complexity theory
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs
- Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution
- Deterministic Parallel Algorithms for Fooling Polylogarithmic Juntas and the Lovász Local Lemma
- Nonrepetitive colorings of graphs
- Lopsidependency in the Moser-Tardos Framework
- Finding independent transversals efficiently
- Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovász Local Lemma
- New bounds for the Moser‐Tardos distribution
- The Moser--Tardos Framework with Partial Resampling
- New Constructive Aspects of the Lovász Local Lemma
- Deterministic Algorithms for the Lovász Local Lemma
- Moser and tardos meet Lovász
- Solving some discrepancy problems in NC
- Algorithms for Weighted Independent Transversals and Strong Colouring
- A New Notion of Commutativity for the Algorithmic Lovász Local Lemma
This page was built for publication: Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
