Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-088 | 31st May 2015 08:10

Exponential Separation of Communication and External Information


Authors: Anat Ganor, Gillat Kol, Ran Raz
Publication: 31st May 2015 08:14
Downloads: 1581


We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with external information complexity $\leq O(k)$, with respect to any input distribution, and distributional communication complexity $\geq 2^k$, with respect to some input distribution. In particular, this shows that a communication protocol cannot always be compressed to its external information. By a result of Braverman [Bra12], our gap is the largest possible.

Moreover, since the upper bound of $O(k)$ on the external information complexity of the problem is obtained with respect to any input distribution, our result implies an exponential gap between communication complexity and information complexity (both internal and external) in the non-distributional setting of Braverman [Bra12]. In this setting, no gap was previously known, even for internal information complexity.

ISSN 1433-8092 | Imprint