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, we 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 Yael Tauman Kalai.
Meeting ID: 898 8493 4058