STOC2020

Interactive error resilience beyond 2/7

Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena

5 citations

Abstract

Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against?