# Binary Interactive Error Resilience Beyond 1/8 (or why (1/2)^3>1/8)

## Author(s): Efremenko, Klim; Kol, Gillat; Saxena, Raghuvansh

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1226n
DC FieldValueLanguage
dc.contributor.authorEfremenko, Klim-
dc.contributor.authorKol, Gillat-
dc.contributor.authorSaxena, Raghuvansh-
dc.date.accessioned2021-10-08T19:51:01Z-
dc.date.available2021-10-08T19:51:01Z-
dc.date.issued2020en_US
dc.identifier.citationEfremenko, Klim, Gillat Kol, and Raghuvansh R. Saxena. "Binary Interactive Error Resilience Beyond 1/8 (or why (1/2)^3>1/8)." In IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (2020): pp. 470-481. doi:10.1109/FOCS46700.2020.00051en_US
dc.identifier.issn1523-8288-
dc.identifier.urihttps://eccc.weizmann.ac.il/report/2021/051/-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1226n-
dc.description.abstractInteractive 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 1 /4. They also give a binary interactive error correcting protocol that only communicates bits and is resilient to 1 /2 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.en_US
dc.format.extent470 - 481en_US
dc.language.isoen_USen_US
dc.relation.ispartofIEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)en_US
dc.rightsAuthor's manuscripten_US
dc.titleBinary Interactive Error Resilience Beyond 1/8 (or why (1/2)^3>1/8)en_US
dc.typeConference Articleen_US
dc.identifier.doi10.1109/FOCS46700.2020.00051-
dc.identifier.eissn2575-8454-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat