Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-166 | 5th November 2010 21:25

Towards Coding for Maximum Errors in Interactive Communication


Authors: Mark Braverman, Anup Rao
Publication: 5th November 2010 21:25
Downloads: 1825


We show that it is possible to encode any communication protocol
between two parties so that the protocol succeeds even if a $(1/4 -
\epsilon)$ 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 -\epsilon$ fraction of errors.

ISSN 1433-8092 | Imprint