DIMACS Theoretical Computer Science Seminar

Title: Towards Coding for Maximum Errors in Interactive Communication

Speaker: Mark Braverman, Princeton University

Date: Wednesday, February 1, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


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.

If time permits we will discuss recent effort in the direction of making the construction more efficient.

Joint work with Anup Rao.

See: http://paul.rutgers.edu/~yixinxu/theory-spring12.html