Multi-party Interactive Coding

Multi-party Interactive Coding - Allison Lewko

Allison Lewko
Columbia University; Member, School of Mathematics
December 3, 2013
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.