Optimal Interactive Coding for Insertions, Deletions, and Substitutions
Optimal Interactive Coding for Insertions, Deletions, and Substitutions
复制标题
插入、删除和替换的最佳交互式编码
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Pei Wu
中科院分区：
文献类型：
--
作者：
Alexander A. Sherstov;Pei Wu
由舒尔曼（Schulman）开创的交互式编码（focs 92，STOC 93）涉及使通信协议具有弹性的对抗噪声。规范模型允许对手在通过通信通道时根据对手自由裁量选择的一小部分恒定符号分数。 Braverman，Gelles，Mao和Ostrovsky（2015）提出了对该模型的深远概括，因此对手可以通过删除和插入符号来额外操纵通道。他们展示了如何使用恒定大小的字母和通信中的恒定因素开销来忠实地模拟该模型中的任何协议，最高为1/18。我们在此广义替换，插入和删除模型中对任何协议进行了最佳模拟，可容忍损坏率高达1/4，同时使字母保持恒定大小，并将通信开销到恒定因素。我们的腐败宽容与腐败率1/4的不可能结果相匹配，即使仅替换就可以造成腐败率（Braverman and Rao，STOC 11）。
Interactive coding, pioneered by Schulman (FOCS 92, STOC 93), 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 adversarys 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. They showed how to faithfully simulate any protocol in this model with corruption rate up to 1/18, 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 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 11).