Title: What are the languages that have bounded k-wise communication complexity?
Speaker: Mario Szegedy, Rutgers University
Date: February 21, 2006 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
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 complexity bounded by a constant are exactly those recognized by programs over commutative monoids (Szegedy93). This can be used to show that these languages all lie in shallow ACC^0.
In contrast, we use locally testable codes to show that three players can recognize languages of arbitrary circuit complexity in constant communication. 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.
Joint with Arkadev Chattopadhyay, Andreas Krebs, Pascal Tesson and Denis Therien