Computer Science/Discrete Mathematics Seminar II

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.