|COMPUTER SCIENCE/DISCRETE MATH I|
|Topic:||Languages with Bounded Multiparty Communication Complexity|
|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.