Skip to main content

LIST and unique coding for interactive communication in the presence of adversarial noise

Author(s): Braverman, Mark; Efremenko, K

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1bt75
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorEfremenko, K-
dc.date.accessioned2019-08-29T17:04:53Z-
dc.date.available2019-08-29T17:04:53Z-
dc.date.issued2017en_US
dc.identifier.citationBraverman, M, Efremenko, K. (2017). LIST and unique coding for interactive communication in the presence of adversarial noise. SIAM Journal on Computing, 46 (388 - 428. doi:10.1137/141002001en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1bt75-
dc.description.abstractIn this paper, we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to 1/2 - ϵ, and that this is tight. Using our list-decodable construction, we study a more nuanced model of noise where the adversary can corrupt up to a fraction α of Alice's communication and up to a fraction β of Bob's communication. We use list decoding to characterize fully the region RU of pairs (α, β) for which unique decoding with a constant rate is possible. The region RU turns out to be quite unusual in its shape. In particular, it is bounded by a piecewise-differentiable curve with infinitely many pieces. We show that outside this region the rate must be exponential. This suggests that in some error regimes, list decoding is necessary for optimal unique decoding. We also consider the setting where only one party of the communication must output the correct answer. We precisely characterize the region of all pairs (α, β) for which one-sided unique decoding is possible in such a way that Alice will output the correct answer.en_US
dc.format.extent388 - 428en_US
dc.language.isoen_USen_US
dc.relation.ispartofSIAM Journal on Computingen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleLIST and unique coding for interactive communication in the presence of adversarial noiseen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1137/141002001-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
LIST and unique coding for interactive communication in the presence of adversarial noise.pdf509.53 kBAdobe PDFView/Download


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