Languages with Bounded Multiparty Communication Complexity

0041539 - MÚ 2007 RIV DE eng V - Research Report
Chattopadhyay, A. - Koucký, Michal - Kreb, A. - Szegedy, M. - Tesson, P.
Languages with Bounded Multiparty Communication Complexity.
[Report TR06-117.]
Trier: Electronic Colloquium on Computational Complexity, 2006. 17 s. ISSN 1433-8092
Institutional research plan: CEZ:AV0Z10190503
Keywords : communication complexity * codes * Ramsey theory
Subject RIV: BA - General Mathematics

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can be computed by shallow ACC0 circuits. In contrast, we use coding techniques to show that there languages of arbitrarily circuit complexity that can be computed by players using constant communication, if k > = 3. However, if the language has a neutral letter and constant communication complexity for k players 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 communication complexity for some fixed k if it has bounded 2-party communication complexity.

Studujeme výpočetní složitost jazyků s konstantní komunikační složitostí.
Permanent Link: http://hdl.handle.net/11104/0134983