Title: Optimal rate list decoding over bounded alphabets using algebraic-geometric codes,
Abstract: We give new constructions of two classes of algebraic code families which are
efficiently list decodable with small output list size from a fraction
$1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any
desired positive constant $\epsilon$. The alphabet size depends only $\epsilon$
and is nearly-optimal.
The first class of codes are obtained by folding algebraic-geometric codes
using automorphisms of the underlying function field. The list decoding
algorithm is based on a linear-algebraic approach, which pins down the
candidate messages to a subspace with a nice "periodic" structure. The list is
pruned by precoding into a special form of "subspace-evasive" sets, which are
constructed pseudorandomly. Instantiating this construction with the
Garcia-Stichtenoth function field tower yields codes list-decodable up to a
$1-R-\epsilon$ error fraction with list size bounded by $O(1/\epsilon)$,
matching the existential bound up to constant factors. The parameters we
achieve are thus quite close to the existential bounds in all three aspects:
error-correction radius, alphabet size, and list-size.
The second class of codes are obtained by restricting evaluation points of an
algebraic-geometric code to rational points from a subfield. Once again, the
linear-algebraic approach to list decoding to pin down candidate messages to a
periodic subspace. We develop an alternate approach based on "subspace designs"
to precode messages. Together with the subsequent explicit constructions of
subspace designs, this yields a deterministic construction of an algebraic code
family of rate $R$ with efficient list decoding from $1-R-\epsilon$ fraction of
errors over a constant-sized alphabet. The list size is bounded by a very
slowly growing function of the block length $N$; in particular, it is at most
$O(\log^{(r)} N)$ (the $r$'th iterated logarithm) for any fixed integer $r$.