Coding for interactive communication correcting insertions and deletions

Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky

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

8 Scopus citations

Abstract

We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties "out of sync", so that there is no consensus regarding the current round of the protocol. In this more general noise model, we obtain the first interactive coding scheme that has a constant rate and tolerates noise rates of up to 1/18-ϵ. To this end we develop a novel primitive we name edit distance tree code. The edit distance tree code is designed to replace the Hamming distance constraints in Schulman's tree codes (STOC 93), with a stronger edit distance requirement. However, the straightforward generalization of tree codes to edit distance does not seem to yield a primitive that suffices for communication in the presence of synchronization problems. Giving the "right" definition of edit distance tree codes is a main conceptual contribution of this work.

Original languageEnglish (US)
Title of host publication43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
EditorsYuval Rabani, Ioannis Chatzigiannakis, Davide Sangiorgi, Michael Mitzenmacher
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770132
DOIs
StatePublished - Aug 1 2016
Event43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 - Rome, Italy
Duration: Jul 12 2016Jul 15 2016

Publication series

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

Other

Other43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
CountryItaly
CityRome
Period7/12/167/15/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Coding
  • Edit distance
  • Interactive communication

Fingerprint Dive into the research topics of 'Coding for interactive communication correcting insertions and deletions'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Gelles, R., Mao, J., & Ostrovsky, R. (2016). Coding for interactive communication correcting insertions and deletions. In Y. Rabani, I. Chatzigiannakis, D. Sangiorgi, & M. Mitzenmacher (Eds.), 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 [61] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 55). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2016.61