Skip to main content

Explicit Capacity Approaching Coding for Interactive Communication

Author(s): Gelles, Ran; Haeupler, Bernhard; Kol, Gillat; Ron-Zewi, Noga; Wigderson, Avi

To refer to this page use:
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/logn)) 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)].
Publication Date: Oct-2018
Citation: Gelles, Ran, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, and Avi Wigderson. "Explicit Capacity Approaching Coding for Interactive Communication." IEEE Transactions on Information Theory 64, no. 10 (2018): pp. 6546-6560. doi:10.1109/TIT.2018.2829764
DOI: 10.1109/TIT.2018.2829764
ISSN: 0018-9448
EISSN: 1557-9654
Pages: 6546 - 6560
Type of Material: Journal Article
Journal/Proceeding Title: IEEE Transactions on Information Theory
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.