Multi-party Interactive Coding

Computer Science/Discrete Mathematics Seminar II
Topic:Multi-party Interactive Coding
Speaker:Allison Lewko
Affiliation:Columbia University; Member, School of Mathematics
Date:Tuesday, December 3
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2013/1203-AllisonLewko

We will discuss interactive coding in the setting where there are n parties attempting to compute a joint function of their inputs using error-prone pairwise communication channels. We will present a general protocol that allows one to achieve only a constant multiplicative overhead in communication complexity compared to the error-free case in the presence of adversarial error. We will discuss the implications in other error models as well, and some accompanying lower bounds. This is joint work with Abhishek Jain and Yael Kalai.