Tata Institute of Fundamental Research
Towards Coding for Maximum Errors in Interactive Communication
Seminar
Speaker:
Swagato Sanyal
Date:
Wednesday, 30 Nov 2011, 14:00 to 15:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
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.
| Speaker: | Swagato Sanyal |
| Date: | Wednesday, 30 Nov 2011, 14:00 to 15:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
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.