[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR
 
 
Tuesday, February 4, 2014
3:00 p.m.
Ryerson 251


Klim Efremenko
University of Chicago
klimefrem at gmail.com
 
Title: “List and Unique Coding of  Interactive Communication”
 
 
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-\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.

Hosts: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140129/47113d26/attachment.htm