Languages with Bounded Multiparty Communication Complexity

COMPUTER SCIENCE/DISCRETE MATH I
Topic:Languages with Bounded Multiparty Communication Complexity
Speaker:Mario Szegedy
Affiliation:Rutgers, The State University of New Jersey
Date:Monday, October 9
Time/Room:11:15am - 12:15pm/West Building Lecture Theatre

We uncover the structure of those languages that have bounded (by a constant) k-party communication complexity in the input on the forehead model, no matter how we partition the input bits into k disjoint sets. This generalizes an earlier result of S. which solves the same problem for k=2. The new result shows that the case of k=3 or larger is significantly more complex than the case of k=2. The work is joint with A. Chattopadhyay, M. Koucky, A. Krebs, P.Tesson, and D. Therien.