High-Rate Codes with Sublinear Time Decoding

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