ECCC-Report TR21-051https://eccc.weizmann.ac.il/report/2021/051Comments and Revisions published for TR21-051en-usFri, 09 Apr 2021 07:15:46 +0300
Paper TR21-051
| Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$) |
Raghuvansh Saxena,
Klim Efremenko,
Gillat Kol
https://eccc.weizmann.ac.il/report/2021/051Interactive 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 $1/4$. They also give a binary interactive error correcting protocol that only communicates bits and is resilient to $1/8$ fraction of errors, but leave the optimality of this scheme as an open problem.
We answer this question in the negative, breaking the $1/8$ barrier. Specifically, we give a binary interactive error correcting scheme that is resilient to $5/39 > 1/8$ fraction of adversarial errors. Our scheme builds upon a novel construction of binary list-decodable interactive codes with small list size.Fri, 09 Apr 2021 07:15:46 +0300https://eccc.weizmann.ac.il/report/2021/051