Binary interactive error resilience beyond

Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE Computer Society
Pages470-481
Number of pages12
ISBN (Electronic)9781728196213
DOIs
StatePublished - Nov 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2020-November
ISSN (Print)0272-5428

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Country/TerritoryUnited States
CityVirtual, Durham
Period11/16/2011/19/20

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Communication Complexity
  • Error Resilience
  • Interactive Coding

Fingerprint

Dive into the research topics of 'Binary interactive error resilience beyond'. Together they form a unique fingerprint.

Cite this