Computer Science/Discrete Mathematics Seminar II

Multi-party Interactive Coding

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.

Date & Time

December 03, 2013 | 10:30am – 12:30pm

Location

S-101

Affiliation

Columbia University; Member, School of Mathematics