High-rate codes with sublinear-time decoding

by Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin.

Oded's comments

While most research of locally decodable codes (LDCs) refers to constant locality, the question of what rate can be achieved at larger (but still non-trivial) levels of locality is also interesting. Furthermore, recently Zeev Dvir [CCC'10] made a couple of conjectures regarding this range of parameters, and showed that they would imply progress in arithmetic circuit complexity. The current work makes a first step in the study of this range of parameters, and it is actually a very significant step (which, in particlar, refutes one of Dvir's conjectures).

Addendum (July 2011): Of independent interest is a presentation of a new variant of Reed-Muller codes, called Multiplicity Codes. See the third paragraph in the following abstract.

Paper posted on ECCC as TR10-148.

The original abstract (slightly revised by O.G.)

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^\eps)$ were known only for codes of rate that decreases faster than any polynomial in $\eps$, where $k$ is the length of the message. Furthermore, for codes of rate strictly greater than half, 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 $\eps>0$ and $r<1$, for infinitely many $k$, there exists a code C that encodes messages of length $k$ with rate $r$, and is locally decodable from a constant fraction of errors using $O(k^\eps)$ 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.

Back to list of Oded's choices.