New Locally Decodable Codes from Lifting
Madhu Sudan (Microsoft Research)
Locally decodable codes (LDCs) are error-correcting codes that
allow for highly-efficient recovery of "pieces" of information
even after arbitrary corruption of a codeword. Locally testable codes
(LTCs) are those that allow for highly-efficient testing to see
if some given word is close to a codeword. Codes derived from
evaluations of low-degree multivariate polynomials give the simplest
example of LDCs and LTCs, and these codes and their locality properties
played a significant role in many results in complexity theory in the
90s. Attempts to construct better LTCs and LDCs (those that offer better
coding efficiency, while achieving a desired level of locality) have
been quite successful in the past decade. However the constructions
often tend to be complex and have inevitably led to codes which satisfy
one of the two properties, but not both! In this talk we will show
how small codes can be lifted to longer ones retaining the locality
of the small ones, while achieving high rate. In particular we give
codes of rate close to arbitrarily one with locality $n^\epsilon$
for arbitrary $\epsilon > 0$. The only previous LDCs with such properties
are the multiplicity codes of Kopparty, Saraf, and Yekhanin. Our codes
are naturally LTCs also, whereas this aspect remains open for the
multiplicity codes.
We will use these codes as an excuse to give an overview of some of
the work in "affine-invariant codes" - of which lifted codes are a
subclass. The testability and rate of our lifted codes follows from
some of the analysis of the general class. One surprising fact that
leads to our high-rate codes is that the set of multivariate functions
that project to a univariate polynomial of degree d on every line, is
*not* the set of degree d multivariate polynomials, but an overwhelmingly
larger set over fields of small characteristic. This fact turns out to
lead to some strong lower bounds on the size of "Nikodym sets" (sets that
contain "most points of at least one line" through every point in the space).
Joint work with Alan Guo (MIT) and Swastik Kopparty (Rutgers)