ECCC-Report TR10-148https://eccc.weizmann.ac.il/report/2010/148Comments and Revisions published for TR10-148en-usThu, 23 Sep 2010 16:59:20 +0200
Paper TR10-148
| High-rate codes with sublinear-time decoding |
Swastik Kopparty,
Shubhangi Saraf,
Sergey Yekhanin
https://eccc.weizmann.ac.il/report/2010/148Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered 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 its 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(k^{\epsilon})$ were known only for codes of rate $\epsilon^{\Omega(1/\epsilon)}$, where $k$ is the length of the message. Furthermore, for codes of rate $> 1/2$, no nontrivial locality has been achieved.
In this paper we construct 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 $k$, there exists a
code $C$ which encodes messages of length $k$ with rate $1 - \alpha$, and is locally decodable from a constant
fraction of errors using $O(k^{\epsilon})$ queries and time.
These codes, which we call multiplicity codes, are based on evaluating multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial based codes; they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in the rate and minimum distance.Thu, 23 Sep 2010 16:59:20 +0200https://eccc.weizmann.ac.il/report/2010/148