Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMMUNICATION COMPRESSION:
Reports tagged with communication compression:
TR14-049 | 11th April 2014
Anat Ganor, Gillat Kol, Ran Raz

#### Exponential Separation of Information and Communication

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint