Skip to main content

Coding for interactive communication correcting insertions and deletions

Author(s): Braverman, Mark; Gelles, R; Mao, J; Ostrovsky, R

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1vt7b
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorGelles, R-
dc.contributor.authorMao, J-
dc.contributor.authorOstrovsky, R-
dc.date.accessioned2019-08-29T17:04:51Z-
dc.date.available2019-08-29T17:04:51Z-
dc.date.issued2016en_US
dc.identifier.citationBraverman, M, Gelles, R, Mao, J, Ostrovsky, R. (2016). Coding for interactive communication correcting insertions and deletions. 55 (10.4230/LIPIcs.ICALP.2016.61en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1vt7b-
dc.description.abstractWe 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.en_US
dc.language.isoen_USen_US
dc.relation.ispartofIEEE Transactions on Information Theoryen_US
dc.rightsAuthor's manuscripten_US
dc.titleCoding for interactive communication correcting insertions and deletionsen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.4230/LIPIcs.ICALP.2016.61-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
Coding for interactive communication correcting insertions and deletions.pdf290 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.