TY - GEN
T1 - Towards coding for maximum errors in interactive communication
AU - Braverman, Mark
AU - Rao, Anup
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
KW - error-correcting codes
KW - interactive computation
KW - tree codes
UR - http://www.scopus.com/inward/record.url?scp=79959750976&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79959750976&partnerID=8YFLogxK
U2 - 10.1145/1993636.1993659
DO - 10.1145/1993636.1993659
M3 - Conference contribution
AN - SCOPUS:79959750976
SN - 9781450306911
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 159
EP - 166
BT - STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
PB - Association for Computing Machinery
T2 - 43rd ACM Symposium on Theory of Computing, STOC 2011
Y2 - 6 June 2011 through 8 June 2011
ER -