Towards optimal deterministic coding for interactive communication

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

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

17 Scopus citations

Abstract

We study efficient, deterministic interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length. For channels that flip bits independently with probability ∈ < 1/2, our coding scheme achieves a communication rate of 1-0(√/H(∈)) and a failure probability of exp(-n/logn) in length n protocols. Prior to our work, all nontrivial deterministic schemes (either efficient or not) had a rate bounded away from 1. Furthermore, the best failure probability achievable by an efficient deterministic coding scheme with constant rate was only quasi-polynomial, i.e., of the form exp(-log(1) n) (Braverman, ITCS 2012). For channels in which an adversary controls the noise pattern our coding scheme can tolerate ω(1/log n) fraction of errors with rate approaching 1. Once more, all previously known nontrivial deterministic schemes (either efficient or not) in the adversarial setting had a rate bounded away from 1, and no nontrivial efficient deterministic coding schemes were known with any constant rate. Essential to both results is an explicit, efficiently encod-able and decodable systematic tree code of length n that has relative distance ω(1/log n) and rate approaching 1, defined over an 0(logn)-bit alphabet. No nontrivial tree code (either efficient or not) was known to approach rate 1, and no nontrivial distance bound was known for any efficient constant rate tree code. The fact that our tree code is systematic, turns out to play an important role in obtaining rate 1-0(√/H(∈)) in the random error model, and approaching rate 1 in the adversarial error model. A central contribution in deriving our coding schemes for random and adversarial errors, is a novel code-concatenation scheme, a notion standard in coding theory which we adapt for the interactive setting. We use the above tree code as the "outer code" in this concatenation. The necessary deterministic "inner code" is achieved by a non-trivial derandomization of the randomized interactive coding scheme of (Haeupler, STOC 2014). This deterministic coding scheme (with exponential running time, but applied here to O(logn) bit blocks) can handle an e fraction of adversarial errors with a communication rate of 1-0(√/H(∈)).

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages1922-1936
Number of pages15
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Externally publishedYes
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume3

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Towards optimal deterministic coding for interactive communication'. Together they form a unique fingerprint.

  • Cite this

    Gelles, R., Haeupler, B., Kol, G., Ron-Zewi, N., & Wigderson, A. (2016). Towards optimal deterministic coding for interactive communication. In R. Krauthgamer (Ed.), 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 (pp. 1922-1936). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 3). Association for Computing Machinery. https://doi.org/10.1137/1.9781611974331.ch135