Skip to main content

Toward Coding for Maximum Errors in Interactive Communication

Author(s): Braverman, Mark; Rao, Anup

To refer to this page use:
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.
Publication Date: 2014
Citation: Braverman, Mark, and Anup Rao. "Toward Coding for Maximum Errors in Interactive Communication." IEEE Transactions on Information Theory 60, no. 11 (2014): pp. 7248-7255. doi:10.1109/TIT.2014.2353994
DOI: 10.1109/TIT.2014.2353994
ISSN: 0018-9448
EISSN: 1557-9654
Pages: 7248 - 7255
Type of Material: Journal Article
Journal/Proceeding Title: IEEE Transactions on Information Theory
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.