We construct 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 on $\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 second class of codes are obtained by restricting evaluation points of an algebraic-geometric code to rational points from a subfield. In both cases, we develop a linear-algebraic approach to perform list decoding, which pins down the candidate messages to a subspace with a nice "periodic" structure.
To prune this subspace and obtain a good bound on the list-size, we pick subcodes of these codes by pre-coding into certain subspace-evasive sets which are guaranteed to have small intersection with the sort of periodic subspaces that arise in our list decoding. We develop two approaches for constructing such subspace-evasive sets. The first is a Monte Carlo construction of hierearchical subspace-evasive (h.s.e) sets which leads to excellent list-size but is not explicit. The second approach exploits a further ultra-periodicity of our subspaces and uses a novel construct called subspace designs, which were subsequently constructed explicitly and also found further applications in pseudorandomness.
To get a family of codes over a fixed alphabet size, we instantiate our approach with algebraic-geometric codes based on the Garcia-Stichtenoth tower of function fields. Combining this with pruning via h.s.e sets yields codes list-decodable up to a $1-R-\epsilon$ error fraction with list size bounded by $O(1/\epsilon)$, matching the existential bound for random codes up to constant factors. Further, the alphabet size can be made $\exp(\tilde{O}(1/\epsilon^2))$ which is not much worse than the lower bound of $\exp(\Omega(1/\epsilon))$. The parameters we achieve are thus quite close to the existential bounds in all three aspects---error-correction radius, alphabet size, and list-size---simultaneously. This construction is, however, Monte Carlo and the claimed list decoding property only holds with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time $O_\epsilon(N^c)$ for an absolute constant $c$, where $N$ is the code's block length.
Using subspace designs instead for the pruning, our approach yields a deterministic construction of an algebraic code family of rate $R$ with efficient list decoding from $1-R-\epsilon$ fraction of errors over an alphabet of constant size $\exp(\tilde{O}(1/\epsilon^2))$. The list size bound is upper 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$. The explicit construction avoids the shortcoming of the Monte Carlo sampling at the expense of a worse list size.
