Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Amortized Communication Complexity:
TR13-079 | 2nd June 2013
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Direct Sum Fails for Zero Error Average Communication

We show that in the model of zero error communication complexity, direct sum fails for average communication complexity as well as for external information cost. Our example also refutes a version of a conjecture by Braverman et al. that in the zero error case amortized communication complexity equals external information ... more >>>

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