2014 · 42 citations · 11 references
EngineeringCommunicationComputer ScienceCryptographyDigital CommunicationInformation TheoryChannel CodingCoding TheoryError-correcting CodesInformation-theoretic SecurityInteractive CommunicationRobustness In Secure ComputationSecurity Properties Of Protocols
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 α Alice's communication and up to a fraction β of Bob's communication. We use list-decoding in order to fully characterize 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 a way that Alice will output the correct answer.
11
List decoding for noisy channels
Peter Eliaš · 1957 · 338 citations
Coding for interactive communication
Leonard J. Schulman · IEEE Transactions on Information Theory · 1996 · 194 citations
Rounds in Communication Complexity Revisited
Noam Nisan, Avi Wigderson · SIAM Journal on Computing · 1993 · 169 citations
Efficient and Explicit Coding for Interactive Communication
Ran Gelles, Ankur Moitra, Amit Sahai · 2011 · 63 citations
Efficient Interactive Coding against Adversarial Noise
Zvika Brakerski, Yael Tauman Kalai · 2012 · 58 citations