arXiv preprint ·
LOCAL LLL in $\operatorname{poly}(\log\log n)$ Rounds
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We provide a $\operatorname{poly}(\log\log n)$-round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion $pd^{c} < 1$, for a sufficiently large constant $c$. The best previous general round complexity was $\widetilde O(\log n)$. The key ingredient is a local reduction that amplifies the LLL probability exponent quadratically, while increasing the dependency radius only by a constant factor.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Improved Combinatorial Auctions with and without Samples
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Stochastic Weighted Caching with Per-Request Predictions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.