Towards coding for maximum errors in interactive communication

Mark Braverman, Anup Rao

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

57 Scopus citations

Abstract

We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4-ε) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing the communication in the protocol by a constant factor (the constant depends on epsilon). This encoding uses a constant sized alphabet. This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication and tolerating a (1/8-ε) fraction of errors.

Original languageEnglish (US)
Title of host publicationSTOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
Pages159-166
Number of pages8
DOIs
StatePublished - 2011
Event43rd ACM Symposium on Theory of Computing, STOC'11 - San Jose, CA, United States
Duration: Jun 6 2011Jun 8 2011

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other43rd ACM Symposium on Theory of Computing, STOC'11
CountryUnited States
CitySan Jose, CA
Period6/6/116/8/11

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • error-correcting codes
  • interactive computation
  • tree codes

Fingerprint Dive into the research topics of 'Towards coding for maximum errors in interactive communication'. Together they form a unique fingerprint.

Cite this