Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Theory Seminar: List and Unique Coding of Interactive Communication
event speaker icon
Klim Efremenko (Tel Aviv University)
event date icon
Wednesday, 23.4.2014, 12:30
event location icon
Taub 201
In this talk 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 will show how to use list-decoding in order to fully characterize the region $R$ of pairs $(\alpha, \beta)$ for which unique decoding with constant rate is possible. The region $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. Joint work with Mark Braverman.
[Back to the index of events]