Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-079 | 1st May 2017 01:41

#### Optimal Interactive Coding for Insertions, Deletions, and Substitutions

TR17-079
Authors: Alexander A. Sherstov, Pei Wu
Publication: 1st May 2017 01:58
Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky (2015) proposed a far-reaching generalization of this model, whereby the adversary can additionally manipulate the channel by removing and inserting symbols. For any $\epsilon>0,$ they showed how to faithfully simulate any protocol in this model with corruption rate up to $1/18-\epsilon,$ using a constant-size alphabet and a constant-factor overhead in communication.
We give an optimal simulation of any protocol in this generalized model of substitutions, insertions, and deletions, tolerating a corruption rate up to $1/4-\epsilon$ while keeping the alphabet to a constant size and the communication overhead to a constant factor. Our corruption tolerance matches an impossibility result for corruption rate $1/4$ which holds even for substitutions alone (Braverman and Rao, STOC 2011).