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

16 Citations (Scopus)

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 known that proving explicit congested clique lower bounds is as difficult as proving circuit lower bounds. In this work, we use various more traditional complexity theory tools to build a clearer picture of the complexity landscape of the congested clique: \beginitemize ıtem Nondeterminism and beyond: We introduce the nondeterministic congested clique model (analogous to NP) and show that there is a natural canonical problem family that captures all problems solvable in constant time with nondeterministic algorithms. We further generalise these notions by introducing the constant-round decision hierarchy (analogous to the polynomial hierarchy). ıtem Non-constructive lower bounds: We lift the prior non-uniform counting arguments to a general technique for proving non-constructive uniform lower bounds for the congested clique. In particular, we prove a time hierarchy theorem for the congested clique, showing that there are decision problems of essentially all complexities, both in the deterministic and nondeterministic settings. ıtem Fine-grained complexity: We map out relationships between various natural problems in the congested clique model, arguing that a reduction-based complexity theory currently gives us a fairly good picture of the complexity landscape of the congested clique.
Original languageEnglish
Title of host publicationSPAA’18, Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
PublisherACM
Pages163-172
Number of pages10
ISBN (Electronic)978-1-4503-5799-9
DOIs
Publication statusPublished - 2018
MoE publication typeA4 Conference publication
EventAnnual ACM Symposium on Parallelism in Algorithms and Architectures - Vienna, Austria
Duration: 16 Jul 201818 Jul 2018
Conference number: 30

Conference

ConferenceAnnual ACM Symposium on Parallelism in Algorithms and Architectures
Abbreviated titleSPAA
Country/TerritoryAustria
CityVienna
Period16/07/201818/07/2018

Fingerprint

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

Cite this