A candidate for a strong separation of information and communication

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

2 Scopus citations

Abstract

The weak interactive compression conjecture asserts that any two-party communication protocol with communication complexity C and information complexity I can be compressed to a protocol with communication complexity poly(I)polylog(C). We describe a communication problem that is a candidate for refuting that conjecture. Specifically, while we show that the problem can be solved by a protocol with communication complexity C and information complexity I = polylog(C), the problem seems to be hard for protocols with communication complexity poly(I)polylog(C) = polylog(C).

Original languageEnglish (US)
Title of host publication9th Innovations in Theoretical Computer Science, ITCS 2018
EditorsAnna R. Karlin
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770606
DOIs
StatePublished - Jan 1 2018
Event9th Innovations in Theoretical Computer Science, ITCS 2018 - Cambridge, United States
Duration: Jan 11 2018Jan 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume94
ISSN (Print)1868-8969

Other

Other9th Innovations in Theoretical Computer Science, ITCS 2018
CountryUnited States
CityCambridge
Period1/11/181/14/18

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 'A candidate for a strong separation of information and communication'. Together they form a unique fingerprint.

Cite this