Exponential Separation of Information and Communication

by Anat Ganor, Gillat Kol, and Ran Raz

Oded's comments

I think the abstract talks for itself. I'd only stress that this is a general communication task (i.e., solving a search problem rather than a decision problem), and that the result refers to arbitrary communication protocols (rather than to constant-round ones).

Update by Gillat (July 2014): The separation was extended to Boolean functions, rather than relations.

The original abstract

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman, our gap is the largest possible. By a result of Braverman and Rao, our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.

see ECCC TR14-049.

Back to list of Oded's choices.