TY - JOUR

T1 - Exponential separation of communication and external information

AU - GANOR, ANAT

AU - KOL, GILLAT

AU - RAZ, RAN

N1 - Publisher Copyright:
© 2021 Society for Industrial and Applied Mathematics Publications. All rights reserved.

PY - 2021

Y1 - 2021

N2 - We show an exponential gap between communication complexity and external infor- mation complexity by analyzing a communication task suggested as a candidate by Braverman [A Hard-to-Compress Interactive Task?, in Proceedings of the 51th Annual Allerton Conference on Communication, Control, and Computing, IEEE, 2013]. Previously, only a separation of commu- nication complexity and internal information complexity was known. More precisely, we obtain an explicit example of a search problem with external information complexity at most O(k), with respect to any input distribution, and distributional communication complexity at least 2k, 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 [SIAM J. Comput., 44 (2015), pp. 1698{1739], our gap is the largest possible. Moreover, since the upper bound of O(k) on the ex- ternal 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 nondistributional setting of Braverman [SIAM J. Comput., 44 (2015), pp. 1698{1739]. In this setting, no gap was previously known, even for internal information complexity.

AB - We show an exponential gap between communication complexity and external infor- mation complexity by analyzing a communication task suggested as a candidate by Braverman [A Hard-to-Compress Interactive Task?, in Proceedings of the 51th Annual Allerton Conference on Communication, Control, and Computing, IEEE, 2013]. Previously, only a separation of commu- nication complexity and internal information complexity was known. More precisely, we obtain an explicit example of a search problem with external information complexity at most O(k), with respect to any input distribution, and distributional communication complexity at least 2k, 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 [SIAM J. Comput., 44 (2015), pp. 1698{1739], our gap is the largest possible. Moreover, since the upper bound of O(k) on the ex- ternal 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 nondistributional setting of Braverman [SIAM J. Comput., 44 (2015), pp. 1698{1739]. In this setting, no gap was previously known, even for internal information complexity.

KW - Communication complexity

KW - Communication compression

KW - Information complexity

UR - http://www.scopus.com/inward/record.url?scp=85110402726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85110402726&partnerID=8YFLogxK

U2 - 10.1137/16M1096293

DO - 10.1137/16M1096293

M3 - Article

AN - SCOPUS:85110402726

SN - 0097-5397

VL - 50

SP - 236

EP - 254

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -