Brief announcement: Towards a complexity theory for the congested clique

Janne H. Korhonen, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

5 Citations (Scopus)
41 Downloads (Pure)


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.

Original languageEnglish
Title of host publication31st International Symposium on Distributed Computing, DISC 2017
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959770538
Publication statusPublished - 1 Oct 2017
MoE publication typeA4 Conference publication
EventInternational Symposium on Distributed Computing - Vienna, Austria
Duration: 16 Oct 201720 Oct 2017
Conference number: 31

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN (Electronic)1868-8969


ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC


  • Complexity theory
  • Congested clique
  • Distributed computing


Dive into the research topics of 'Brief announcement: Towards a complexity theory for the congested clique'. Together they form a unique fingerprint.

Cite this