Direct sum fails for zero error average communication

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

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

2 Scopus citations

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 cost. 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 cost. In our examples the underlying distributions do not have full support. One interpretation of a distributions 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)
Title of host publicationITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery
Pages517-522
Number of pages6
ISBN (Print)9781450322430
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States
Duration: Jan 12 2014Jan 14 2014

Publication series

NameITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

Other

Other2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
CountryUnited States
CityPrinceton, NJ
Period1/12/141/14/14

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Direct sum fails for zero error average communication'. Together they form a unique fingerprint.

  • Cite this

    Kol, G., Moran, S., Shpilka, A., & Yehudayoff, A. (2014). Direct sum fails for zero error average communication. In ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science (pp. 517-522). (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science). Association for Computing Machinery. https://doi.org/10.1145/2554797.2554844