COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II | |

Topic: | High-Rate Codes with Sublinear Time Decoding |

Speaker: | Swastik Kopparty |

Affiliation: | Member, School of Mathematics |

Date: | Tuesday, September 28 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/kopparty |

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms, that can recover any bit of the original message by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality O(n^epsilon) were known only for codes of rate O(epsilon^(1/epsilon)), where n is the length of the code. Furthermore, for codes of rate > 1/2, no nontrivial locality has been achieved. In this talk, I will describe a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every epsilon > 0 and alpha > 0, for infinitely many n, there exists a code with length n and rate 1 - alpha, that is locally decodable from a constant fraction of errors using O(n^{epsilon}) queries and time. Joint work with Shubhangi Saraf and Sergey Yekhanin