TY - JOUR
T1 - LIST and unique coding for interactive communication in the presence of adversarial noise
AU - Braverman, Mark
AU - Efremenko, Klim
N1 - Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2017
Y1 - 2017
N2 - In 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.
AB - In 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.
KW - Error-correcting codes
KW - Interactive communication
KW - Tree codes
UR - http://www.scopus.com/inward/record.url?scp=85014463609&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85014463609&partnerID=8YFLogxK
U2 - 10.1137/141002001
DO - 10.1137/141002001
M3 - Article
AN - SCOPUS:85014463609
SN - 0097-5397
VL - 46
SP - 388
EP - 428
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 1
ER -