Exponential separation of information and communication for boolean functions

Anat Ganor, Gillat Kol, Ran Raz

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

We show an exponential gap between communication complexity and information complexity by giving an explicit example of a partial boolean function 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 [2015], our gap is the largest possible. By a result of Braverman and Rao [2014], 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, answering a long-standing open problem. 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)
Article number46
JournalJournal of the ACM
Volume63
Issue number5
DOIs
StatePublished - Nov 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

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