ECCC-Report TR06-117https://eccc.weizmann.ac.il/report/2006/117Comments and Revisions published for TR06-117en-usSun, 10 Sep 2006 20:31:27 +0300-
Paper TR06-117
| Languages with Bounded Multiparty Communication Complexity |
Arkadev Chattopadhyay,
Michal Koucky,
Andreas Krebs,
Mario Szegedy,
Pascal Tesson,
Denis ThÃ©rien
https://eccc.weizmann.ac.il/report/2006/117We 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 ACC^0 circuits.
In contrast, we use coding techniques to show that there are languages of arbitrarily large circuit complexity that can be computed by k players using constant communication, if k >= 3. However, if the langauage has a neutral letter and constant communication complexity for k players for some fixed k, then the langauge 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 iff it has bounded 2-party communication complexity.
Sun, 10 Sep 2006 20:31:27 +0300https://eccc.weizmann.ac.il/report/2006/117