Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds

Abstract

In this paper, we prove that explicit FRS codes and multiplicity codes achieve relaxed generalized Singleton bounds for list size $L\ge 1.$ Specifically, we show the following: (1) FRS code of length $n$ and rate $R$ over the alphabet ${\mathbb{F}}_q^s$ with distinct evaluation points is $\left(\frac{L}{L+1}\left(1-\frac{sR}{s-L+1}\right),L\right)$ list-decodable (LD) for list size $L\in [s]$. (2) Multiplicity code of length $n$ and rate $R$ over the alphabet ${\mathbb{F}}_p^s$ with distinct evaluation points is $\left(\frac{L}{L+1}\left(1-\frac{sR}{s-L+1}\right),L\right)$ LD for list size $L\in [s]$. Choosing $s=\hat{I}˜(1/\hat{I}{\mu }^2)$ and $L=O(1/\hat{I}\mu )$, our results imply that both FRS codes and multiplicity codes achieve LD capacity $1-R-\hat{I}\mu$ with optimal list size $O(1/\hat{I}\mu )$. This exponentially improves the previous state of the art $(1/\hat{I}\mu {)}^{O(1/\hat{I}\mu )}$ established by Kopparty et. al. (FOCS 2018) and Tamo (IEEE TIT, 2024). In particular, our results on FRS codes fully resolve a open problem proposed by Guruswami and Rudra (STOC 2006). Furthermore, our results imply the first explicit constructions of $(1-R-\hat{I}\mu ,O(1/\hat{I}\mu ))$ LD codes of rate $R$ with poly-sized alphabets. Our method can also be extended to analyze the list-recoverability (LR) of FRS codes. We provide a tighter radius upper bound that FRS codes cannot be $(\frac{L+1-\ell }{L+1}(1-\frac{mR}{m-1})+o(1),\ell ,L)$ LR where $m=\lceil {\log }_{\ell }(L+1)\rceil$. We conjecture this bound is almost tight when $L+1={\ell }^a$ for any $a\in {\mathbb{N}}^{\ge 2}$. To give some evidences, we show FRS codes are $\left(\frac{1}{2}-\frac{sR}{s-2},2,3\right)$ LR, which proves the tightness in the smallest non-trivial case. Our bound refutes the possibility that FRS codes could achieve LR capacity $(1-R-\hat{I}\mu ,\ell ,O(\frac{\ell }{\hat{I}}\mu ))$. This implies an intrinsic separation between LD and LR of FRS codes.

STOC 2025