Direct Sum Fails for Zero-Error Average Communication

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Research output: Contribution to journalArticlepeer-review

Abstract

We show that in the model of zero-error communication complexity, direct sum fails for average communication complexity as well as for external information complexity. Our example also refutes a version of a conjecture by Braverman et al. that in the zero-error case amortized communication complexity equals external information complexity. In our examples the underlying distributions do not have full support. One interpretation of a distribution of non full support is as a promise given to the players (the players have a guarantee on their inputs). This brings up the issue of promise versus non-promise problems in this context.

Original languageEnglish (US)
Pages (from-to)782-795
Number of pages14
JournalAlgorithmica
Volume76
Issue number3
DOIs
StatePublished - Nov 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Amortized communication complexity
  • Communication complexity
  • External information
  • Information complexity
  • Promise problems

Fingerprint Dive into the research topics of 'Direct Sum Fails for Zero-Error Average Communication'. Together they form a unique fingerprint.

Cite this