### DIMACS Theoretical Computer Science Seminar

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