Languages with Bounded Multiparty Communication Complexity

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 [20]. This can be used to show that these languages all lie in shallow ACC 0. In contrast, we use different 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, 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 and 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