ECCC-Report TR14-007https://eccc.weizmann.ac.il/report/2014/007Comments and Revisions published for TR14-007en-usFri, 17 Jan 2014 05:03:30 +0200
Paper TR14-007
| List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise |
Klim Efremenko,
Mark Braverman
https://eccc.weizmann.ac.il/report/2014/007In 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-\varepsilon$, 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 $\alpha$ fraction of Alice's communication and up-to $\beta$ fraction of Bob's communication. We use list-decoding in order to fully characterize the region $\mathcal{R}_U$ of pairs $(\alpha, \beta)$ for which unique decoding with constant rate is possible. The region $\mathcal{R}_U$ 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 question what if only one party of the communication must to output the correct answer. We precisely characterize the region of all pairs $(\alpha,\beta)$ for which one-sided unique decoding is possible in a way that Alice will output the correct answer. Fri, 17 Jan 2014 05:03:30 +0200https://eccc.weizmann.ac.il/report/2014/007