Exponential separation of information and communication for boolean functions

Anat Ganor, Gillat Kol, Ran Raz

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

18 Scopus citations

Abstract

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol for a partial boolean function cannot always be compressed to its internal information. By a result of Braverman [3], our gap is the largest possible. By a result of Braverman and Rao [4], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity of boolean functions cannot hold, answering a long standing open problem. Our techniques build on [13], that proved a similar result for relations with very long outputs (double exponentially long in k). In addition to the stronger result, the current work gives a simpler proof, benefiting from the short output length of boolean functions. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages557-566
Number of pages10
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Externally publishedYes
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
CountryUnited States
CityPortland
Period6/14/156/17/15

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Amortized communication complexity
  • Communication complexity
  • Communication compression
  • Direct sum
  • Information complexity

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

  • Cite this

    Ganor, A., Kol, G., & Raz, R. (2015). Exponential separation of information and communication for boolean functions. In STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing (pp. 557-566). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015). Association for Computing Machinery. https://doi.org/10.1145/2746539.2746572