Speaker: |
Madhu Sudan (Harvard John A. Paulson School of Engineering and Applied Sciences 339 Maxwell Dworkin 33 Oxford Street Cambridge, MA 02138.) |

Organiser: |
Prahladh Harsha |

Date: |
Wednesday, 11 Jul 2018, 14:00 to 15:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

In STOC 2017 Haeupler and Shahrasbi introduced an elegant notion that they call a "synchronization string" that modularly converts standard error-correcting codes into edit distance codes with almost no loss in parameters and just a slight loss in alphabet size, while retaining algorithmic tractability of error-correction. A concrete example of such a result (from upcoming work with Haeupler and Shahrasbi, ICALP 2018) we show that for every epsilon, delta and gamma, there exists an alphabet Sigma and integer L and (efficient) coding and decoding schemes over the alphabet Sigma of rate to 1 - delta - epsilon that allow delta fraction deletions and gamma fraction insertions where the decoder outputs a list of at most L codewords that is guaranteed to include the transmitted string. In particular the rate does not depend on gamma and indeed gamma can be much larger than 1!

In this talk I will describe the notion of synchronization strings and this modular reduction from edit distance coding to Hamming distance coding.