Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Exponential Separation of Information and Communication

RSS-Feed




Revision #1
Authors: Anat Ganor, Gillat Kol, Ran Raz
Accepted on: 11th May 2014 02:07
Downloads: 829
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


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.



ISSN 1433-8092 | Imprint