TY - GEN

T1 - Binary interactive error resilience beyond

AU - Efremenko, Klim

AU - Kol, Gillat

AU - Saxena, Raghuvansh R.

N1 - Publisher Copyright:
© 2020 IEEE.

PY - 2020/11

Y1 - 2020/11

N2 - 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.

AB - 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.

KW - Communication Complexity

KW - Error Resilience

KW - Interactive Coding

UR - http://www.scopus.com/inward/record.url?scp=85100346964&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85100346964&partnerID=8YFLogxK

U2 - 10.1109/FOCS46700.2020.00051

DO - 10.1109/FOCS46700.2020.00051

M3 - Conference contribution

AN - SCOPUS:85100346964

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 470

EP - 481

BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020

PB - IEEE Computer Society

T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020

Y2 - 16 November 2020 through 19 November 2020

ER -