Interactive Error Correcting Codes

Abstract: Consider the task of communicating a message x to a receiver in an error resilient way. Classically, error correcting codes provide a non-interactive solution to this problem: the sender can simply encode x using an error correcting code, so that even if a constant fraction of the bits are adversarially corrupted, the receiver can still correctly learn x. In this talk, I will define the notion of an interactive error correcting code and show that over a binary alphabet, they can tolerate more adversarial erasures than can (non-interactive) error correcting codes. This is joint work with Meghal Gupta and Yael Tauman Kalai.

Computer scienceMathematicsPhysics

Audience: researchers in the topic

MIT Simple Person's Applied Mathematics Seminar