Name
Abstract | ||
|---|---|---|
Locally 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∈) were known only for codes of rate ∈Ω(1/∈), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality had been achieved. In this article, 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 ∈ > 0 and α > 0, for infinitely many k, there exists a code C which encodes messages of length k with rate 1 − α, and is locally decodable from a constant fraction of errors using O(k∈) 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 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/2629416 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
algorithms,decodable code,derivatives,multiplicity code,locally decodable codes,efficient local decoding algorithm,high-rate code,locally correctable codes,efficient decoding algorithm,nontrivial locality,low rate,sublinear-time algorithms,high rate,rate exp,reliability,theory,sublinear-time decoding,decoding algorithm,multiplicity codes,constant rate,coding and information theory,polynomials,locally decodable code,asymptotic behavior,error correction code | Journal | 61 |
Issue | ISSN | Citations |
5 | 0004-5411 | 22 |
PageRank | References | Authors |
1.30 | 42 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Swastik Kopparty | 1 | 384 | 32.89 |
| Shubhangi Saraf | 2 | 263 | 24.55 |
| Sergey Yekhanin | 3 | 983 | 52.33 |