Interactive channel capacity

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

74 Scopus citations

Abstract

We study the interactive channel capacity of an ε-noisy channel. The interactive channel capacity C(ε) is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate ε, where the communication com- plexity tends to infinity. Our main result is the upper bound C(ε) ≤ 1-Ω (√H(ε) ) : This compares with Shannon's non-interactive channel ca- pacity of 1 - H(ε). In particular, for a small enough ε, our result gives the first separation between interactive and non- interactive channel capacity, answering an open problem by Schulman [6]. We complement this result by the lower bound C(ε) ≥ 1-O (√H(ε) ) ; proved for the case where the players take alternating turns.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages715-724
Number of pages10
DOIs
StatePublished - 2013
Externally publishedYes
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

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

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
Country/TerritoryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Com- munication complexity
  • Information theory
  • Interactive channel capacity
  • The entropy function

Fingerprint

Dive into the research topics of 'Interactive channel capacity'. Together they form a unique fingerprint.

Cite this