Document Open Access Logo

Efficient CONGEST Algorithms for the Lovász Local Lemma

Authors Yannic Maus , Jara Uitto

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.31.pdf
  • Filesize: 0.79 MB
  • 19 pages

Document Identifiers

Author Details

Yannic Maus
  • Technion, Haifa, Israel
Jara Uitto
  • Aalto University, Espoo, Finland

Funding

This project was partially supported by the European Union’s Horizon 2020 Research and Innovation Programme under grant agreement no. 755839 (Yannic Maus).

Cite As Get BibTex

Yannic Maus and Jara Uitto. Efficient CONGEST Algorithms for the Lovász Local Lemma. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.31

Abstract

We present a poly log log n time randomized CONGEST algorithm for a natural class of Lovász Local Lemma (LLL) instances on constant degree graphs. This implies, among other things, that there are no LCL problems with randomized complexity between Ω(log n) and poly log log n. Furthermore, we provide extensions to the network decomposition algorithms given in the recent breakthrough by Rozhoň and Ghaffari [STOC2020] and the follow up by Ghaffari, Grunau, and Rozhoň [SODA2021]. In particular, we show how to obtain a large distance separated weak network decomposition with a negligible dependency on the range of unique identifiers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • distributed graph algorithms
  • CONGEST
  • Lovász Local Lemma
  • locally checkable labelings

Metrics

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

Related Versions

References

  1. Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network decomposition and locality in distributed computation. In Proc. 30th Symp. on Found. of Computer Science (FOCS), pages 364-369, 1989. Google Scholar
  2. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model. In 32nd International Symposium on Distributed Computing, DISC, pages 9:1-9:16, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.9.
  3. Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally checkable labelings with small messages. In International Symposium on Distributed Computing DISC, 2021. Google Scholar
  4. Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1307-1318, 2018. URL: https://doi.org/10.1145/3188745.3188860.
  5. Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Efficient deterministic distributed coloring with small bandwidth. In ACM Symposium on Principles of Distributed Computing (PODC), pages 243-252, 2020. URL: https://doi.org/10.1145/3382734.3404504.
  6. Leonid Barenboim. On the locality of some np-complete problems. In Automata, Languages, and Programming - 39th International Colloquium (ICALP), pages 403-415, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_37.
  7. Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers, 2013. Google Scholar
  8. Leonid Barenboim, Michael Elkin, and Cyril Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. Theor. Comput. Sci., 751:2-23, 2018. URL: https://doi.org/10.1016/j.tcs.2016.07.005.
  9. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM, 63(3):20:1-20:45, 2016. Google Scholar
  10. József Beck. An algorithmic approach to the Lovász local lemma. Random Structures & Algorithms, 2(4):343-365, 1991. Google Scholar
  11. 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 ACM Symposium on Theory of Computing (STOC), 2016. Google Scholar
  12. Sebastian Brandt, Christoph Grunau, and Václav Rozhon. Generalizing the sharp threshold phenomenon for the distributed complexity of the lovász local lemma. In ACM Symposium on Principles of Distributed Computing (PODC), pages 329-338, 2020. URL: https://doi.org/10.1145/3382734.3405730.
  13. Sebastian Brandt, Christoph Grunau, and Václav Rozhon. The randomized local computation complexity of the lovász local lemma. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, ACM Symposium on Principles of Distributed Computing (PODC), pages 307-317. ACM, 2021. URL: https://doi.org/10.1145/3465084.3467931.
  14. Sebastian Brandt, Yannic Maus, and Jara Uitto. A sharp threshold phenomenon for the distributed complexity of the lovász local lemma. In Proceedings of the 2019 ACM Symposium on Principles of Distributed (PODC), pages 389-398, 2019. URL: https://doi.org/10.1145/3293611.3331636.
  15. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. Distributed Comput., 33(3-4):349-366, 2020. URL: https://doi.org/10.1007/s00446-020-00376-1.
  16. Yi-Jun Chang and Mohsen Ghaffari. Strong-diameter network decomposition. the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), abs/2102.09820, 2021. URL: http://arxiv.org/abs/2102.09820.
  17. Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. The complexity of distributed edge coloring with small palettes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2633-2652, 2018. URL: https://doi.org/10.1137/1.9781611975031.168.
  18. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 615-624, 2016. Google Scholar
  19. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. SIAM J. Comput., 48(1):33-69, 2019. URL: https://doi.org/10.1137/17M1157957.
  20. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed Algorithms for the Lovász Local Lemma and Graph Coloring. Distributed Computing, 30(4):261-280, 2017. URL: https://doi.org/10.1007/s00446-016-0287-6.
  21. Janosch Deurer, Fabian Kuhn, and Yannic Maus. Deterministic distributed dominating set approximation in the CONGEST model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 94-103, 2019. URL: https://doi.org/10.1145/3293611.3331626.
  22. Michael Elkin and Ofer Neiman. Distributed strong diameter network decomposition. In Proc. 35th ACM Symp. on Principles of Distributed Computing (PODC), pages 211-216, 2016. Google Scholar
  23. Paul Erdös and László Lovász. Problems and Results on 3-chromatic Hypergraphs and some Related Questions. Colloquia Mathematica Societatis János Bolyai, pages 609-627, 1974. Google Scholar
  24. Manuela Fischer and Mohsen Ghaffari. Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy. In the Proceedings of the 31st International Symposium on Distributed Computing (DISC), pages 18:1-18:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.18.
  25. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proc. 27th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 270-277, 2016. Google Scholar
  26. Mohsen Ghaffari, Christoph Grunau, and Václav Rozhoň. Improved deterministic network decomposition. In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. URL: http://arxiv.org/abs/2007.08253.
  27. Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 662-673, 2018. URL: https://doi.org/10.1109/FOCS.2018.00069.
  28. Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On Derandomizing Local Distributed Algorithms. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 662-673, 2018. Google Scholar
  29. Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. Improved distributed δ-coloring. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 427-436, 2018. URL: https://dl.acm.org/citation.cfm?id=3212764.
  30. Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In 32nd International Symposium on Distributed Computing (DISC), pages 29:1-29:17, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.29.
  31. Mohsen Ghaffari and Fabian Kuhn. On the use of randomness in local distributed graph algorithms. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 290-299, 2019. URL: https://doi.org/10.1145/3293611.3331610.
  32. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In ACM Symposium on Theory of Computing (STOC), pages 784-797, 2017. URL: https://doi.org/10.1145/3055399.3055471.
  33. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In ACM Symposium on Theory of Computing (STOC), pages 784-797. ACM, 2017. Google Scholar
  34. Mohsen Ghaffari and Julian Portmann. Improved network decompositions using small messages with applications on mis, neighborhood covers, and beyond. In 33rd International Symposium on Distributed Computing (DISC), pages 18:1-18:16, 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.18.
  35. Magnús M. Halldórsson, Fabian Kuhn, and Yannic Maus. Distance-2 coloring in the CONGEST model. In ACM Symposium on Principles of Distributed Computing (PODC), pages 233-242, 2020. URL: https://doi.org/10.1145/3382734.3405706.
  36. Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin. Coloring fast without learning your neighbors' colors. In 34th International Symposium on Distributed Computing (DISC), pages 39:1-39:17, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.39.
  37. Nati Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  38. Nati Linial and Michael Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  39. Robin A. Moser and Gábor Tardos. A Constructive Proof of the General Lovász Local Lemma. J. ACM, pages 11:1-11:15, 2010. Google Scholar
  40. M. Naor and L. Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. Google Scholar
  41. Alessandro Panconesi and Aravind Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms, 20(2):581-592, 1995. Google Scholar
  42. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  43. Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In ACM Symposium on Theory of Computing (STOC), pages 350-363, 2020. 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