Languages with bounded multiparty communication complexity

Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

We study languages with bounded communication complexity in the multiparty "input on the forehead model" with worst-case partition. In the two-party case, languages with bounded complexity are exactly those recognized by programs over commutative monoids [19]. This can be used to show that these languages all lie in shallow ACC0. In contrast, we use coding techniques to show that there are languages of arbitrarily large circuit complexity which can be recognized in constant communication by k players for k ≥ 3. However, we show that if a language has a neutral letter and bounded communication complexity in the k-party game for some fixed k then the language is in fact regular. We give an algebraic characterization of regular languages with this property. We also prove that a symmetric language has bounded k-party complexity for some fixed k iff it has bounded two party complexity.

Original languageEnglish (US)
Title of host publicationSTACS 2007 - 24th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
PublisherSpringer Verlag
Pages500-511
Number of pages12
ISBN (Print)9783540709176
DOIs
StatePublished - 2007
Event24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007 - Aachen, Germany
Duration: Feb 22 2007Feb 24 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4393 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007
Country/TerritoryGermany
CityAachen
Period2/22/072/24/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Languages with bounded multiparty communication complexity'. Together they form a unique fingerprint.

Cite this