Interactive Error Resilience and the Surprising Power of Feedback

Опубликовано 16 февраля 2021, 18:15

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.