[Colloquium] [Staff] Theory Seminars at Computer Science
Donna Brooms
donna at cs.uchicago.edu
Wed May 30 10:42:03 CDT 2012
Date: Tuesday, June 5, 2012
Time: 3 p.m.
Place: Ryerson 251, 1100 E. 58th Street
_________________________
Speaker: Mark Braverman
From: Princeton University
Title: Towards Coding for Maximum Errors in Interactive Communication
Abstract:
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 Anup Rao.
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120530/6a48109d/attachment.htm
More information about the Colloquium
mailing list