Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR14-049 | 11th May 2014 02:07

#### Exponential Separation of Information and Communication

Revision #1
Authors: Anat Ganor, Gillat Kol, Ran Raz
Accepted on: 11th May 2014 02:07
Keywords:

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.

Changes to previous version:

A simplification of the construction and the lower bound proof. The upper bound is somewhat more involved, but is still relatively easy.
We also added a general tool to upper bound the information complexity of a protocol.

### Paper:

TR14-049 | 11th April 2014 07:23

#### Exponential Separation of Information and Communication

TR14-049
Authors: Anat Ganor, Gillat Kol, Ran Raz
Publication: 11th April 2014 07:28
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.