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