Type of Talk: UTCS Colloquia

Speaker/Affiliation: Anup Rao

/University of Washington

Talk Audience: UTCS Faculty and Graduate Stu

dents

Date/Time: Wednesday, May 18, 2011, 11:00 a.m.

Location:
ACES 2.402

Host: David Zuckerman

Talk Title: Towards Coding for

Maximum Errors in Interactive Communication

Talk Abstract: We show th

at 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 s

ymbols 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 a

lphabet. This improves on an earlier result of Schulman, who showed how t

o recover when the fraction of errors is bounded by 1/240. We also show ho

w to simulate an arbitrary protocol with a protocol using the binary alpha

bet, a constant factor increase in communication and tolerating a 1/8 - e

psilon fraction of errors.