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 -