License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.61
URN: urn:nbn:de:0030-drops-61981
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6198/
Go to the corresponding LIPIcs Volume Portal

Braverman, Mark ; Gelles, Ran ; Mao, Jieming ; Ostrovsky, Rafail

Coding for Interactive Communication Correcting Insertions and Deletions

pdf-format:
LIPIcs-ICALP-2016-61.pdf (0.6 MB)

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 - epsilon. 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.

BibTeX - Entry

@InProceedings{braverman_et_al:LIPIcs:2016:6198,
  author =	{Mark Braverman and Ran Gelles and Jieming Mao and Rafail Ostrovsky},
  title =	{{Coding for Interactive Communication Correcting Insertions and Deletions}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6198},
  URN =		{urn:nbn:de:0030-drops-61981},
  doi =		{10.4230/LIPIcs.ICALP.2016.61},
  annote =	{Keywords: Interactive communication, coding, edit distance}
}

Keywords: Interactive communication, coding, edit distance
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI