TY - JOUR
T1 - Exponential separation of communication and external information
AU - GANOR, ANAT
AU - KOL, GILLAT
AU - RAZ, RAN
N1 - Funding Information:
∗Received by the editors October 3, 2016; accepted for publication (in revised form) August 8, 2018; published electronically October 24, 2019. A preliminary version appeared in STOC 2016. https://doi.org/10.1137/16M1096293 Funding: The first author was supported by an Israel Science Foundation grant 552/16, by the I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation grant 4/11. The second author was supported by National Science Foundation grant CCF-1750443. The third author was supported by the Israel Science Foundation grant 1402/14, by the I-CORE Program of the Planning and Budgeting Committee, and the Israel Science Foundation, by the Simons Collaboration on Algorithms and Geometry, by the Fund for Math at IAS, and by the National Science Foundation grants CCF-1412958 and CCF-1714779. †Tel-Aviv University, 6997801 Tel Aviv, Israel (anat.ganor@gmail.com). ‡Princeton University, Princeton, NJ 08540 (gillat.kol@gmail.com, ran.raz.mail@gmail.com).
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 -