TY - JOUR
T1 - Coding for Interactive Communication Correcting Insertions and Deletions
AU - Braverman, Mark
AU - Gelles, Ran
AU - Mao, Jieming
AU - Ostrovsky, Rafail
N1 - Funding Information:
Manuscript received May 29, 2016; revised November 21, 2016 and May 27, 2017; accepted July 17, 2017. Date of publication August 2, 2017; date of current version September 13, 2017. This work was supported in part by the NSF CAREER under Award CCF-1149888, in part by NSF under Grant CCF-1215990, in part by the Turing Centenary Fellowship, in part by the Packard Fellowship in Science and Engineering, in part by the Simons Collaboration on Algorithms and Geometry, in part by NSF under Grant 09165174, Grant 1065276, Grant 1118126, and Grant 1136174, in part by DARPA, in part by the U.S.–Israel BSF under Grant 2008411, in part by the OKAWA Foundation Research Award, in part by the IBM Faculty Research Award, in part by the Xerox Faculty Research Award, in part by the B. John Garrick Foundation Award, in part by the Teradata Research Award, and in part by the Lockheed-Martin Corporation Research Award. A short version of this paper [9] was presented at the 2016 ICALP.
Publisher Copyright:
© 2017 IEEE.
PY - 2017/10
Y1 - 2017/10
N2 - 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.
AB - 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.
KW - Interactive communication
KW - adversarial noise
KW - coding protocols
KW - noise resilience
UR - http://www.scopus.com/inward/record.url?scp=85028912904&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028912904&partnerID=8YFLogxK
U2 - 10.1109/TIT.2017.2734881
DO - 10.1109/TIT.2017.2734881
M3 - Article
AN - SCOPUS:85028912904
SN - 0018-9448
VL - 63
SP - 6256
EP - 6270
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 10
M1 - 8000379
ER -