Title: Informational Complexity and Lower Bounds in Communication Complexity

Speaker: Amit Chakrabarti, Institute for Advanced Study

Date: November 12, 2002, 4:30-5:30

Location: CoRE Building, room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We introduce the notion of Informational Complexity of communication protocols, which measures the amount of information about the players' inputs revealed by the messages they send. This is in contrast to the usual measure of communication complexity which simply measures the number of bits sent.

Using our new notion we prove new lower bounds in the Simultaneous Message model of communication. The two-player $n$-bit equality problem is well known to have complexity $\Theta(\sqrt n)$. We prove that solving $m$ copies of the problem (i.e., a direct sum problem) has complexity $\Omega(m \sqrt n)$. We also prove similar lower bounds on certain Boolean combinations of multiple copies of the equality function. These results can be generalised to a broader class of functions.

This is joint work with Yaoyun Shi, Anthony Wirth, and Andrew Yao.