Exponential separation of information and communication

Anat Ganor, Gillat Kol, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

Abstract

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.

Original languageEnglish (US)
Title of host publicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PublisherIEEE Computer Society
Pages176-185
Number of pages10
ISBN (Electronic)9781479965175
DOIs
StatePublished - Dec 7 2014
Externally publishedYes
Event55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 - Philadelphia, United States
Duration: Oct 18 2014Oct 21 2014

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
CountryUnited States
CityPhiladelphia
Period10/18/1410/21/14

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Information complexity
  • amortized communication complexity
  • communication complexity
  • communication compression
  • direct sum

Fingerprint Dive into the research topics of 'Exponential separation of information and communication'. Together they form a unique fingerprint.

  • Cite this

    Ganor, A., Kol, G., & Raz, R. (2014). Exponential separation of information and communication. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 176-185). [6979002] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). IEEE Computer Society. https://doi.org/10.1109/FOCS.2014.27