Klim Efremenko

Interactive error correcting codesInteractive 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. What is the largest fraction of corruptions that such codes can protect against? If the error-resilient protocol is allowed to communicate large (constant sized) symbols, Braverman and Rao (STOC, 2011) show that the maximum rate of corruptions that can be tolerated is. They also give a binary interactive error correcting protocol that only communicates bits and is resilient to fraction of errors, but leave the optimality of this scheme as an open problem. We answer this question in the negative, breaking the barrier. Specifically, we give a binary interactive error correcting scheme that is resilient to fraction of adversarial errors. Our scheme builds upon a novel construction of binary list-decodable interactive codes with small list size.