LIPIcs.DISC.2017.55.pdf
- Filesize: 371 kB
- 3 pages
Document
Brief Announcement: Towards a Complexity Theory for the Congested Clique
Authors
-
Part of:
Volume:
31st International Symposium on Distributed Computing (DISC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-10-12
Cite As Get BibTex
Janne H. Korhonen and Jukka Suomela. Brief Announcement: Towards a Complexity Theory for the Congested Clique. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 55:1-55:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.55
Abstract
The congested clique model of distributed computing has been receiving attention as a model for densely connected distributed systems. While there has been significant progress on the side of upper bounds, we have very little in terms of lower bounds for the congested clique; indeed, it is now know that proving explicit congested clique lower bounds is as difficult as proving circuit lower bounds. In this work, we use traditional complexity-theoretic tools to build a clearer picture of the complexity landscape of the congested clique, proving non-constructive lower bounds and studying the relationships between natural problems.
Subject Classification
Keywords
- distributed computing
- congested clique
- complexity theory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Benny Applebaum, Dariusz R. Kowalski, Boaz Patt-Shamir, and Adi Rosén. Clique here: On the distributed complexity in fully-connected networks. Parallel Processing Letters, 26(01):1650004, 2016. URL: http://dx.doi.org/10.1142/S0129626416500043.
- Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, and Dennis Olivetti. What can be verified locally? In Proc. 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66, pages 8:1-8:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2017.8.
-
Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In Proc. 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pages 615-624, 2016.
-
Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model, 2017. arXiv:1704.06297 [cs.DC].
- Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proc. 33rd ACM Symposium on Principles of Distributed Computing (PODC 2014), pages 367-376, 2014. URL: http://dx.doi.org/10.1145/2611462.2611493.
- Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. A hierarchy of local decision. In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55, pages 118:1-118:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.118.
-
Juris Hartmanis and Richard E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285-306, 1965.
-
Janne H. Korhonen and Jukka Suomela. Towards a complexity theory for the congested clique, 2017. arXiv:1705.03284 [cs.DC].
- Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. URL: http://dx.doi.org/10.1137/S0097539793254571.