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.