Spring 2015

Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks

Thursday, April 23rd, 2015 9:30 am10:45 am

Add to Calendar

Klim Efremenko: In this talk 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 alpha of Alice's communication and up to a fraction beta  of Bob's communication. We use list-decoding in order to fully characterize the region of pairs (alpha, beta) for which unique decoding with a constant rate is possible. This region  turns out to be quite unusual in its shape.

Ran Gelles: We will discuss the task of multiparty computation performed over networks (of arbitrary topology) in the presence of random noise. We will set the model and survey several coding schemes which plot an interesting relation between the specific topology and the rate of the coding scheme.  Specifically, we will discuss a scheme by Rajagopalan and Schulman whose rate is O(1/log (d+1)), where d is the maximal degree of connectivity in the network. Additionally, we will discuss a recent scheme by Alon, Braverman, Efremenko, Gelles and Haeupler which achieves a constant rate O(1) for a large family of topologies including complete graphs and random graphs with n vertices and degrees n^{\Omega(1)}.