TY - GEN
T1 - Exponential separation of communication and external information
AU - Ganor, Anat
AU - Kol, Gillat
AU - Raz, Ran
N1 - Funding Information:
Research supported by an Israel Science Foundation grant and by the I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation. Research supported by the National Science Foundation grant No. CCF-1412958 and the Weizmann Institute of Science National Postdoctoral Award Program for Advancing Women in Science. Research supported by the Israel Science Foundation grant No. 1402/14, by the I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation, by a grant from the Simons Foundation, by the Fund for Math at IAS, and by the National Science Foundation grant No. CCF-1412958.
PY - 2016/6/19
Y1 - 2016/6/19
N2 - We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman. Previously, only a separation of communication complexity and internal information complexity was known. More precisely, we obtain an explicit example of a search problem with external information complexity ≤ O(k), with respect to any input distribution, and distributional communication complexity ≥ 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, 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. In this setting, no gap was previously known, even for internal information complexity.
AB - We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman. Previously, only a separation of communication complexity and internal information complexity was known. More precisely, we obtain an explicit example of a search problem with external information complexity ≤ O(k), with respect to any input distribution, and distributional communication complexity ≥ 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, 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. 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=84979265925&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979265925&partnerID=8YFLogxK
U2 - 10.1145/2897518.2897535
DO - 10.1145/2897518.2897535
M3 - Conference contribution
AN - SCOPUS:84979265925
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 977
EP - 986
BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Mansour, Yishay
A2 - Wichs, Daniel
PB - Association for Computing Machinery
T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
Y2 - 19 June 2016 through 21 June 2016
ER -