Janne H. Korhonen · Jukka Suomela

Brief announcement: Towards a complexity theory for the congested clique

DISC 2017 · 31st International Symposium on Distributed Computing, Vienna, Austria, October 2017 · doi:10.4230/LIPIcs.DISC.2017.55

authors’ version publisher’s version arXiv.org

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 instead use various more 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.

Publication

Andréa W. Richa (Ed.): 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 55:1–55:3, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017

ISBN 978-3-95977-053-8

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.