High-Rate Codes with Sublinear Time Decoding
Video of this lecture
| 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 |
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