Computer Science/Discrete Mathematics Seminar I | |

Topic: | Towards Coding for Maximum Errors in Interactive Communication |

Speaker: | Mark Braverman |

Affiliation: | Princeton University |

Date: | Monday, December 5 |

Time/Room: | 11:15am - 12:15pm/S-101 |

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.