We show new and improved list decoding properties of folded Reed-Solomon (RS) codes and multiplicity codes.
Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances
in coding theory: Folded RS codes were the first known explicit construction of \emph{capacity-achieving} list decodable codes (Guruswami and Rudra, {\em IEEE Trans. Information Theory}, 2010), and multiplicity codes were the first construction of \emph{high-rate} locally decodable codes (Kopparty, Saraf, and Yekhanin, {\em J. ACM}, 2014).

In this work, we show that folded RS codes and multiplicity codes are in fact better than was previously known in the context of list decoding and local list decoding.
Our first main result shows that folded RS codes achieve list decoding capacity with {\em constant} list sizes, independent of the block length. Prior work with constant list sizes first obtained list sizes that are polynomial in the block length, and relied on pre-encoding with subspace evasive sets to reduce the list sizes to a constant (Guruswami and Wang, {\em IEEE Trans. Information Theory}, 2012; Dvir and Lovett, {\em STOC}, 2012). The list size we obtain is $(1/\epsilon)^{O(1/\epsilon)}$ where $\epsilon$ is the gap to capacity, which matches the list size obtained by pre-encoding with subspace evasive sets.

For our second main result, we observe that {\em univariate} multiplicity codes exhibit similar behavior, and use this, together with additional ideas, to show that {\em multivariate} multiplicity codes are {\em locally} list decodable \emph{up to their minimum distance}.
By known reductions, this gives in turn capacity-achieving locally list decodable codes with query complexity $\exp( \tilde O((\log N)^{5/6}))$. This improves on the tensor-based construction of (Hemenway, Ron-Zewi, and Wootters, {\em SICOMP}, 2019), which gave capacity-achieving locally list decodable codes of query complexity
$N^{\tilde O(1/\log \log N)}$, and is close to the best known query complexity of $\exp( \tilde O(\sqrt{\log N}))$ for high-rate locally (uniquely) decodable codes (Kopparty, Meir, Ron-Zewi, and Saraf, {\em J. ACM}, 2017).

Revised and simplified Sections 4 and 5, and added running times of local list decoder.

We show new and improved list decoding properties of folded Reed-Solomon (RS) codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory: Folded RS codes were the first known explicit construction of \emph{capacity-achieving} list decodable codes (Guruswami and Rudra, {\em IEEE Trans. Information Theory}, 2010), and multiplicity codes were the first construction of \emph{high-rate} locally decodable codes (Kopparty, Saraf, and Yekhanin, {\em J. ACM}, 2014).

In this work, we show that folded RS codes and multiplicity codes are in fact better than was previously known in the context of list decoding and local list decoding. Our first main result shows that folded RS codes achieve list decoding capacity with {\em constant} list sizes, independent of the block length. Prior work with constant list sizes first obtained list sizes that are polynomial in the block length, and relied on pre-encoding with subspace evasive sets to reduce the list sizes to a constant (Guruswami and Wang, {\em IEEE Trans. Information Theory}, 2012; Dvir and Lovett, {\em STOC}, 2012). The list size we obtain is $(1/\epsilon)^{O(1/\epsilon)}$ where $\epsilon$ is the gap to capacity, which matches the list size obtained by pre-encoding with subspace evasive sets.

For our second main result, we observe that {\em univariate} multiplicity codes exhibit similar behavior, and use this, together with additional ideas, to show that {\em multivariate} multiplicity codes are {\em locally} list decodable \emph{up to their minimum distance}. By known reductions, this gives in turn capacity-achieving locally list decodable codes with query complexity $\exp( \tilde O((\log N)^{5/6}))$. This improves on the tensor-based construction of (Hemenway, Ron-Zewi, and Wootters, {\em SICOMP}, 2019), which gave capacity-achieving locally list decodable codes of query complexity $N^{\tilde O(1/\log \log N)}$, and almost matches the best known query complexity of $\exp( \tilde O(\sqrt{\log N}))$ for high-rate locally (uniquely) decodable codes (Kopparty, Meir, Ron-Zewi, and Saraf, {\em J. ACM}, 2017).

Some improvements and simplifications over the previous version, including a completely elementary proof showing that both folded Reed-Solomon and univariate multiplicity codes (even when the degree is larger than the field size) are list-decodable up to capacity with constant list sizes, and a result showing that multivariate multiplicity codes are locally list decodable up to their minimum distance.

For simplicity and clarity, we have also decided to omit some of the results from the previous version, including an alphabet reduction for our codes via multilevel concatenation, analyzing the running time of our local list decoder, and a slight improvement in the query complexity of our local list decoder. We have commented about all omissions inside the manuscript.

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions of codes known to achieve list-decoding capacity; multivariate multiplicity codes were the first constructions of high-rate locally correctable codes; and univariate multiplicity codes are also known to achieve list-decoding capacity.

However, previous analyses of the error-correction properties of these codes did not yield optimal results. In particular, in the list-decoding setting, the guarantees on the list-sizes were polynomial in the block length, rather than constant; and for multivariate multiplicity codes, local list-decoding algorithms could not go beyond the Johnson bound.

In this paper, we show that Folded Reed-Solomon codes and multiplicity codes are in fact better than previously known in the context of list-decoding and local list-decoding. More precisely, we first show that Folded RS codes achieve list-decoding capacity with {\em constant} list sizes, independent of the block length; and that high-rate univariate multiplicity codes can also be list-recovered with constant list sizes. Using our result on univariate multiplicity codes, we show that multivariate multiplicity codes are high-rate, {\em locally} list-recoverable codes. Finally, we show how to combine the above results with standard tools to obtain capacity achieving locally list decodable codes with query complexity significantly lower than was known before.