Theory of Computing
-------------------
Title     : List-Decoding Multiplicity Codes
Authors   : Swastik Kopparty
Volume    : 11
Number    : 5
Pages     : 149-182
URL       : https://theoryofcomputing.org/articles/v011a005

Abstract
--------

We study the list-decodability of multiplicity codes. These codes,
which are based on evaluations of high-degree polynomials and their
derivatives, have rate approaching 1 while simultaneously allowing
for sublinear-time error correction. In this paper, we show that
multiplicity codes also admit powerful list-decoding and local list-
decoding algorithms that work even in the presence of a large error
fraction. In other words, we give algorithms for recovering a
polynomial given several evaluations of it and its derivatives, where
possibly many of the given evaluations are incorrect.

Our first main result shows that univariate multiplicity codes over
fields of prime order can be list-decoded up to the so-called "list-
decoding capacity." Specifically, we show that univariate multiplicity
codes of rate $R$ over fields of prime order can be list-decoded from
a $(1- R - \epsilon)$ fraction of errors in polynomial time (for
constant $R, \epsilon$). This resembles the behavior of the "Folded
Reed-Solomon Codes" of Guruswami and Rudra (Trans. Info. Theory
2008). The list-decoding algorithm is based on constructing a
differential equation of which the desired codeword is a solution;
this differential equation is then solved using a power-series
approach (a variation of Hensel lifting) along with other algebraic
ideas.

Our second main result is a list-decoding algorithm for decoding
multivariate multiplicity codes up to their Johnson radius. The key
ingredient of this algorithm is the construction of a special family
of "algebraically-repelling" curves passing through the points of
$F_q^m$; no moderate-degree multivariate polynomial over $F_q^m$ can
simultaneously vanish on all these curves. These curves enable us to
reduce the decoding of multivariate multiplicity codes over $F_q^m$
to several instances of decoding univariate multiplicity codes over
the big field $F_{q^m}$, for which such list-decoding algorithms are
known.

As a corollary, we show how multivariate multiplicity codes of length
$n$ and rate nearly $1$ can be locally list-decoded up to their
Johnson radius in $O(n^{\epsilon})$ time.


A version of this paper was posted online as an Electronic Colloq. on 
Computational Complexity Tech. Report.