Coding for Interactive Communication Correcting Insertions and Deletions

Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


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 carefully designed to replace the Hamming distance constraints in Schulman's tree codes (IEEE Trans. Inf. Theory, 1996), with a stronger edit-distance requirement.

Original languageEnglish (US)
Article number8000379
Pages (from-to)6256-6270
Number of pages15
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Oct 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • Interactive communication
  • adversarial noise
  • coding protocols
  • noise resilience


Dive into the research topics of 'Coding for Interactive Communication Correcting Insertions and Deletions'. Together they form a unique fingerprint.

Cite this