Explicit Capacity Approaching Coding for Interactive Communication

Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We show an explicit (that is, efficient and deterministic) capacity approaching interactive coding scheme that simulates any interactive protocol under random errors with nearly optimal communication rate. Specifically, over the binary symmetric channel with crossover probability ∈, our coding scheme achieves a communication rate of 1 - O(√H(∈)), together with negligible exp (-Ω (∈4 n/n)) failure probability (over the randomness of the channel). A rate of 1 - Θ (√H(∈)) is likely asymptotically optimal as a result of Kol and Raz (2013) suggests. Prior to this paper, such a communication rate was achievable only using randomized coding schemes [Kol and Raz (2013); Hauepler (2014)].

Original languageEnglish (US)
Article number8345651
Pages (from-to)6546-6560
Number of pages15
JournalIEEE Transactions on Information Theory
Volume64
Issue number10
DOIs
StatePublished - Oct 2018

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Interactive communication
  • coding protocols
  • deterministic interactive coding
  • tree codes

Fingerprint Dive into the research topics of 'Explicit Capacity Approaching Coding for Interactive Communication'. Together they form a unique fingerprint.

Cite this