Brief announcement: Towards a complexity theory for the congested clique

Janne H. Korhonen, Jukka Suomela

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

5 Sitaatiot (Scopus)
33 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Otsikko31st International Symposium on Distributed Computing, DISC 2017
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut1-3
ISBN (elektroninen)9783959770538
DOI - pysyväislinkit
TilaJulkaistu - 1 lokak. 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Distributed Computing - Vienna, Itävalta
Kesto: 16 lokak. 201720 lokak. 2017
Konferenssinumero: 31

Julkaisusarja

NimiLeibniz International Proceedings in Informatics
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Vuosikerta91
ISSN (elektroninen)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
LyhennettäDISC
Maa/AlueItävalta
KaupunkiVienna
Ajanjakso16/10/201720/10/2017

Sormenjälki

Sukella tutkimusaiheisiin 'Brief announcement: Towards a complexity theory for the congested clique'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä