Computer Science/Discrete Mathematics Seminar I

The Error Resilience of Binary Codes with Interaction

Q1: A fundamental result in coding theory, known as the Plotkin bound, suggests that a binary code can tolerate up to ¼ fraction of adversarial corruptions. Can we design codes that handle more errors if we allow interaction between the sender and receiver, instead of having the sender transmit just a single message?

Q2: Interactive error-correcting codes transform a two-party communication protocol into an error-resilient protocol that functions correctly even if a constant fraction of the transmitted symbols are adversarially corrupted. While 1/8 is a natural limit on the resilience of binary interactive codes, is it possible to break through this barrier?

We answer both of these questions affirmatively and explore the connection between them.

This talk is based on joint research with Klim Efremenko, Raghuvansh R. Saxena, and Zhijun Zhang.

Date & Time

February 10, 2025 | 10:30am – 11:30am

Location

Simonyi 101 and Remote Access

Speakers

Gillat Kol, Princeton University