Brief announcement
| dc.contributor | Aalto-yliopisto | fi |
| dc.contributor | Aalto University | en |
| dc.contributor.author | Korhonen, Janne H. | en_US |
| dc.contributor.author | Suomela, Jukka | en_US |
| dc.contributor.department | Department of Computer Science | en_US |
| dc.date.accessioned | 2017-11-21T13:36:41Z | |
| dc.date.available | 2017-11-21T13:36:41Z | |
| dc.date.issued | 2017-10-01 | en_US |
| dc.description.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. | en |
| dc.description.version | Peer reviewed | en |
| dc.format.extent | 1-3 | |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.citation | Korhonen , J H & Suomela , J 2017 , Brief announcement : Towards a complexity theory for the congested clique . in 31st International Symposium on Distributed Computing, DISC 2017 . , 55 , Leibniz International Proceedings in Informatics , vol. 91 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , pp. 1-3 , International Symposium on Distributed Computing , Vienna , Austria , 16/10/2017 . https://doi.org/10.4230/LIPIcs.DISC.2017.55 | en |
| dc.identifier.doi | 10.4230/LIPIcs.DISC.2017.55 | en_US |
| dc.identifier.isbn | 9783959770538 | |
| dc.identifier.issn | 1868-8969 | |
| dc.identifier.other | PURE UUID: 6afbea39-be27-4f14-a84d-3c52cf62dd8a | en_US |
| dc.identifier.other | PURE ITEMURL: https://research.aalto.fi/en/publications/6afbea39-be27-4f14-a84d-3c52cf62dd8a | en_US |
| dc.identifier.other | PURE LINK: http://www.scopus.com/inward/record.url?scp=85032347159&partnerID=8YFLogxK | en_US |
| dc.identifier.other | PURE FILEURL: https://research.aalto.fi/files/16072577/LIPIcs_DISC_2017_55.pdf | en_US |
| dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/28806 | |
| dc.identifier.urn | URN:NBN:fi:aalto-201711217627 | |
| dc.language.iso | en | en |
| dc.publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | |
| dc.relation.ispartof | International Symposium on Distributed Computing | en |
| dc.relation.ispartofseries | 31st International Symposium on Distributed Computing, DISC 2017 | en |
| dc.relation.ispartofseries | Leibniz International Proceedings in Informatics | en |
| dc.relation.ispartofseries | Volume 91 | en |
| dc.rights | openAccess | en |
| dc.subject.keyword | Complexity theory | en_US |
| dc.subject.keyword | Congested clique | en_US |
| dc.subject.keyword | Distributed computing | en_US |
| dc.title | Brief announcement | en |
| dc.type | Conference article in proceedings | fi |
| dc.type.version | publishedVersion |
