Interactive Error Resilience and the Surprising Power of Feedback

Interactive error correcting codes are codes that encode a two party communication protocol to an error-resilient protocol that succeeds even if a constant fraction of the communicated symbols are adversarially corrupted, at the cost of increasing the communication by a constant factor. The fraction of corruptions that such codes can protect against is called the error resilience. Several recent results have shown that drastic gains in the error resilience can be achieved by using interactive codes that implement “feedback”. I shall be reviewing (at least) two of these works in this talk.

Based on joint works with Klim Efremenko and Gillat Kol.

Speaker Details

Raghuvansh R. Saxena is a graduate student in the Department of Computer Science at Princeton University. Prior to joining Princeton, he received his Bachelor of Technology degree in Computer Science and Engineering from IIT Delhi. Raghuvansh has a wide interest in theoretical computer science, especially in developing new complexity theoretic and coding tools for emergent problems in several areas of computing, such as distributed communication and electronic markets. Many of his works are driven by his search for “efficient” and “practical” solutions to modern day problems. Some of the honors that he has received are the Microsoft PhD Fellowship and a Siebel Scholarship in 2019 and the Presidents Gold Medal (IIT Delhi) in 2016.

Date:
Speakers:
Raghuvansh Saxena
Affiliation:
Princeton University