Document Open Access Logo

The Complexity Landscape of Distributed Locally Checkable Problems on Trees

Author Yi-Jun Chang

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.18.pdf
  • Filesize: 0.93 MB
  • 17 pages

Document Identifiers

Author Details

Yi-Jun Chang
  • ETH Zürich, Switzerland

Cite AsGet BibTex

Yi-Jun Chang. The Complexity Landscape of Distributed Locally Checkable Problems on Trees. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.18

Abstract

Recent research revealed the existence of gaps in the complexity landscape of locally checkable labeling (LCL) problems in the LOCAL model of distributed computing. For example, the deterministic round complexity of any LCL problem on bounded-degree graphs is either O(log^∗ n) or Ω(log n) [Chang, Kopelowitz, and Pettie, FOCS 2016]. The complexity landscape of LCL problems is now quite well-understood, but a few questions remain open. For bounded-degree trees, there is an LCL problem with round complexity Θ(n^{1/k}) for each positive integer k [Chang and Pettie, FOCS 2017]. It is conjectured that no LCL problem has round complexity o(n^{1/(k-1)}) and ω(n^{1/k}) on bounded-degree trees. As of now, only the case of k = 2 has been proved [Balliu et al., DISC 2018]. In this paper, we show that for LCL problems on bounded-degree trees, there is indeed a gap between Θ(n^{1/(k-1)}) and Θ(n^{1/k}) for each k ≥ 2. Our proof is constructive in the sense that it offers a sequential algorithm that decides which side of the gap a given LCL problem belongs to. We also show that it is EXPTIME-hard to distinguish between Θ(1)-round and Θ(n)-round LCL problems on bounded-degree trees. This improves upon a previous PSPACE-hardness result [Balliu et al., PODC 2019].

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed algorithms
  • LOCAL model
  • locally checkable labeling

Metrics

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

Related Versions

References

  1. Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. The distributed complexity of locally checkable problems on paths is decidable. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 262-271. ACM Press, 2019. Google Scholar
  2. Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of distributed binary labeling problems. In Proceedings of the 34th International Symposium on Distributed Computing (DISC), 2020. Google Scholar
  3. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), 2018. Google Scholar
  4. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. How much does randomness help with locally checkable problems? In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC), pages 299-308. ACM, 2020. Google Scholar
  5. 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. ACM, 2018. Google Scholar
  6. Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. Hardness of minimal symmetry breaking in distributed computing. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 369-378, 2019. Google Scholar
  7. Sebastian Brandt. An automatic speedup theorem for distributed problems. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 379-388, 2019. 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 Proceedings of the 48th ACM Symposium on the Theory of Computing (STOC), pages 479-488, 2016. Google Scholar
  9. Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznaundefinedski. LCL problems on grids. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 101-110, 2017. Google Scholar
  10. Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed edge coloring and a special case of the constructive lovász local lemma. ACM Trans. Algorithms, 16(1), 2019. Google Scholar
  11. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the local model. SIAM J. Comput., 48(1):122-143, 2019. Google Scholar
  12. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the local model. SIAM J. Comput., 48(1):33-69, 2019. Google Scholar
  13. Yi-Jun Chang, Jan Studený, and Jukka Suomela. Distributed graph problems through an automata-theoretic lens. arXiv:2002.07659, 2020. Google Scholar
  14. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the Lovász local lemma and graph coloring. Distributed Computing, 30:261-280, 2017. Google Scholar
  15. Manuela Fischer and Mohsen Ghaffari. Sublogarithmic distributed algorithms for Lovász local lemma with implications on complexity hierarchies. In Proceedings of the 31st International Symposium on Distributed Computing (DISC), pages 18:1-18:16, 2017. Google Scholar
  16. Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In Proceedings of 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 662-673, 2018. Google Scholar
  17. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. Google Scholar
  18. Gary L. Miller and John H. Reif. Parallel tree contraction-Part I: fundamentals. Advances in Computing Research, 5:47-72, 1989. Google Scholar
  19. Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259-1277, 1995. Google Scholar
  20. Dennis Olivetti. Brief announcement: Round eliminator: A tool for automatic speedup simulation. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC), pages 352-354. ACM, 2020. Google Scholar
  21. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  22. Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 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 Imprint Privacy Contact