Klim Efremenko (Theory Seminar W14)

"List and Unique Coding of Interactive Communication"
Klim Efremenko
(University of Chicago)
Monday, February 24th, 2014, 2:00pm
EBU3B, Room 4140
Abstract:
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-epsilon, 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 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.