Towards Coding for Maximum Errors in Interactive Communication

  • Anup Rao | University of Washington

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. Joint work with Mark Braverman.

发言人详细信息

Anup Rao is an Assistant Professor at the University of Washington. He was a researcher at Princeton, a member of the Institute For Advanced Study, and a graduate student at the University of Texas at Austin under David Zuckerman.

接下来观看