Abstract
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)}.