| 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.