Dr Peter Davies-Peck peter.w.davies@durham.ac.uk
Assistant Professor
Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring
Davies, Peter
Authors
Abstract
The Lovász Local Lemma is a classic result in probability theory that is often used to prove the existence of combinatorial objects via the probabilistic method. In its simplest form, it states that if we have n ‘bad events’, each of which occurs with probability at most p and is independent of all but d other events, then under certain criteria on p and d, all of the bad events can be avoided with positive probability. While the original proof was existential, there has been much study on the algorithmic Lovász Local Lemma: that is, designing an algorithm which finds an assignment of the underlying random variables such that all the bad events are indeed avoided. Notably, the celebrated result of Moser and Tardos [JACM ’10] also implied an efficient distributed algorithm for the problem, running in O(log2 n) rounds. For instances with low d, this was improved to O(d 2 + logO(1) log n) by Fischer and Ghaffari [DISC ’17], a result that has proven highly important in distributed complexity theory (Chang and Pettie [SICOMP ’19]). We give an improved algorithm for the Lovász Local Lemma, providing a trade-off between the strength of the criterion relating p and d, and the distributed round complexity. In particular, in the same regime as Fischer and Ghaffari’s algorithm, we improve the round complexity to O( d log d + logO(1) log n). At the other end of the trade-off, we obtain a logO(1) log n round complexity for a substantially wider regime than previously known. As our main application, we also give the first logO(1) log n-round distributed algorithm for the problem of ∆+o(∆)-edge coloring a graph of maximum degree ∆. This is an almost exponential improvement over previous results: no prior logo(1) n-round algorithm was known even for 2∆ − 2-edge coloring.
Citation
Davies, P. (2023, January). Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring. Presented at ACM-SIAM Symposium on Discrete Algorithms (SODA23), Florence, Italy
Presentation Conference Type | Conference Paper (published) |
---|---|
Conference Name | ACM-SIAM Symposium on Discrete Algorithms (SODA23) |
Start Date | Jan 22, 2023 |
End Date | Jan 25, 2023 |
Acceptance Date | Oct 17, 2023 |
Online Publication Date | Jan 16, 2023 |
Publication Date | Jan 16, 2023 |
Deposit Date | Nov 4, 2022 |
Publicly Available Date | Jul 19, 2023 |
Pages | 4273-4295 |
Book Title | Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |
DOI | https://doi.org/10.1137/1.9781611977554.ch163 |
Public URL | https://durham-repository.worktribe.com/output/1134503 |
Files
Published Conference Proceeding
(792 Kb)
PDF
You might also like
Component stability in low-space massively parallel computation
(2024)
Journal Article
Optimal (degree+1)-Coloring in Congested Clique
(2023)
Presentation / Conference Contribution
Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization
(2023)
Presentation / Conference Contribution
Optimal Message-Passing with Noisy Beeps
(2023)
Presentation / Conference Contribution
Parallel Derandomization for Coloring
(2024)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search