Toward coding for maximum errors in interactive communication

Mark Braverman, Anup Rao

Research output: Contribution to journalArticle

30 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 multiplicative factor that depends only on, using an alphabet whose size depends only on. 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)
Article number6891225
Pages (from-to)7248-7255
Number of pages8
JournalIEEE Transactions on Information Theory
Volume60
Issue number11
DOIs
StatePublished - Nov 2014

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Codes and communication channels

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

  • Cite this