Computer Science/Discrete Mathematics Seminar I

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.