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.
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.