Document Open Access Logo

Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy

Authors Manuela Fischer, Mohsen Ghaffari

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.18.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Author Details

Manuela Fischer
Mohsen Ghaffari

Cite As Get BibTex

Manuela Fischer and Mohsen Ghaffari. Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.18

Abstract

Locally Checkable Labeling (LCL) problems include essentially all the classic problems of LOCAL distributed algorithms. In a recent enlightening revelation, Chang and Pettie [FOCS'17] showed that any LCL (on bounded degree graphs) that has an o(log n)-round randomized algorithm can be solved in T_(LLL)(n) rounds, which is the randomized complexity of solving (a relaxed variant of) the Lovasz Local Lemma (LLL) on bounded degree n-node graphs. Currently, the best known upper bound on T_(LLL)(n) is O(log n), by Chung, Pettie, and Su [PODC'14], while the best known lower bound is Omega(log log n), by Brandt et al. [STOC'16]. Chang and Pettie conjectured that there should be an O(log log n)-round algorithm (on bounded degree graphs).

Making the first step of progress towards this conjecture, and providing a significant improvement on the algorithm of Chung et al. [PODC'14], we prove that T_(LLL)(n)= 2^O(sqrt(log log n)). Thus, any o(log n)-round randomized distributed algorithm for any LCL problem on bounded degree graphs can be automatically sped up to run in 2^O(sqrt(log log n)) rounds.

Using this improvement and a number of other ideas, we also improve the complexity of a number of graph coloring problems (in arbitrary degree graphs) from the O(log n)-round results of Chung, Pettie and Su [PODC'14] to 2^O(sqrt(log log n)). These problems include defective coloring, frugal coloring, and list vertex-coloring.

Subject Classification

Keywords
  • Distributed Graph Algorithms
  • the Lov'{a}sz Local Lemma (LLL)
  • Locally Checkable Labeling problems (LCL)
  • Defective Coloring
  • Frugal Coloring
  • List Ve

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon. A parallel algorithmic version of the local lemma. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 586-593. IEEE, 1991. Google Scholar
  2. Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley &Sons, 2004. Google Scholar
  3. Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Fast distributed network decompositions and covers. J. of Parallel and Distributed Comp., 39(2):105-114, 1996. Google Scholar
  4. Baruch Awerbuch, Michael Luby, Andrew V. Goldberg, and Serge A. Plotkin. Network decomposition and locality in distributed computation. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 364-369, 1989. Google Scholar
  5. Baruch Awerbuch and David Peleg. Sparse partitions. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 503-513, 1990. Google Scholar
  6. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM (JACM), 63(3):20, 2016. Google Scholar
  7. József Beck. An algorithmic approach to the Lovász Local Lemma. I. Random Structures &Algorithms, 2(4):343-365, 1991. Google Scholar
  8. Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed Lovász Local Lemma. In Proc. of the Symp. on Theory of Comp. (STOC), pages 479-488. ACM, 2016. Google Scholar
  9. Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. Deterministic algorithms for the Lovász local lemma. In Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), pages 992-1004, 2010. Google Scholar
  10. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the local model. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), 2016. Google Scholar
  11. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the local model. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), 2017, preprint arXiv:1704.06297. Google Scholar
  12. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the Lovász Local Lemma and graph coloring. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 134-143, 2014. Google Scholar
  13. Artur Czumaj and Christian Scheideler. A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems. In Proc. of the Symp. on Theory of Comp. (STOC), pages 38-47, 2000. Google Scholar
  14. Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 10(2):609-627, 1975. Google Scholar
  15. Manuela Fischer and Mohsen Ghaffari. Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy. preprint arXiv:1705.04840, 2017. URL: https://arxiv.org/abs/1705.04840.
  16. Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 625-634. IEEE, 2016. Google Scholar
  17. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), 2016. Google Scholar
  18. Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), 2017. Google Scholar
  19. David G. Harris. Lopsidependency in the Moser-Tardos framework: Beyond the lopsided Lovász local lemma. ACM Trans. Algorithms, 13(1):17:1-17:26, December 2016. Google Scholar
  20. David G. Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (Δ+ 1)-coloring in sublogarithmic rounds. In Proc. of the Symp. on Theory of Comp. (STOC), pages 465-478, 2016. Google Scholar
  21. David G. Harris and Aravind Srinivasan. The Moser-Tardos framework with partial resampling. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 469-478. IEEE, 2013. Google Scholar
  22. David G. Harris and Aravind Srinivasan. A constructive algorithm for the Lovász local lemma on permutations. In Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), SODA'14, pages 907-925, 2014. Google Scholar
  23. David G. Harris and Aravind Srinivasan. Algorithmic and enumerative aspects of the Moser-Tardos distribution. In Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), pages 2004-2023, 2016. Google Scholar
  24. Kashyap Babu Rao Kolipaka and Mario Szegedy. Moser and Tardos meet Lovász. In Proc. of the Symp. on Theory of Comp. (STOC), pages 235-244, 2011. Google Scholar
  25. Nathan Linial. Distributive graph algorithms - global solutions from local data. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 331-335. IEEE, 1987. Google Scholar
  26. Michael Molloy and Bruce Reed. Further algorithmic aspects of the local lemma. In Proc. of the Symp. on Theory of Comp. (STOC), pages 524-529. ACM, 1998. Google Scholar
  27. Michael Molloy and Bruce Reed. Graph coloring and the probabilistic method, 2002. Google Scholar
  28. Robin A Moser. A constructive proof of the Lovász local lemma. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 343-350. ACM, 2009. Google Scholar
  29. Robin A Moser and Gábor Tardos. A constructive proof of the general Lovász Local Lemma. Journal of the ACM (JACM), 57(2):11, 2010. Google Scholar
  30. Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. Google Scholar
  31. Alessandro Panconesi and Aravind Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proc. of the Symp. on Theory of Comp. (STOC), pages 581-592. ACM, 1992. Google Scholar
  32. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  33. Aravind Srinivasan. Improved algorithmic versions of the Lovász local lemma. In Pro. of ACM-SIAM Symp. on Disc. Alg. (SODA), pages 611-620. Society for Industrial and Applied Mathematics, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact