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

In this paper, we prove that explicit folded Reed–Solomon (RS) codes and univariate multiplicity codes achieve relaxed generalized Singleton bounds for list size L≥1. Specifically, we show the following: (1) Any folded RS code of block length n and rate R over the alphabet Fqs with distinct evaluation points is (L/L+1(1−sR/s−L+1),L) (average-radius) list-decodable for list size L∈[s]. (2) Any univariate multiplicity code of block length n and rate R over the alphabet Fps (where p is a prime) with distinct evaluation points is (L/L+1(1−sR/s−L+1),L) (average-radius) list-decodable for list size L∈[s]. Choosing s=Θ(1/є2) and L=O(1/є), our results imply that both explicit folded RS codes and explicit univariate multiplicity codes achieve list-decoding capacity 1−R−є with optimal list size O(1/є). This exponentially improves the previous state of the art (1/є)O(1/є) established by Kopparty, Ron-Zewi, Saraf, and Wootters (FOCS 2018 or SICOMP, 2023) and Tamo (IEEE TIT, 2024). In particular, our results on folded Reed–Solomon codes fully resolve a long-standing open problem originally proposed by Guruswami and Rudra (STOC 2006 or IEEE TIT, 2008). Furthermore, our results imply the first explicit constructions of (1−R−є,O(1/є)) (average-radius) list-decodable codes of rate R with polynomial-sized alphabets in the literature. Our methodology can also analyze the list-recoverability of folded RS codes. We provide a tighter radius upper bound that states folded RS codes cannot be (L+1−ℓ/L+1(1−mR/m−1)+o(1), ℓ, L) list-recoverable where m=⌈logℓ(L+1)⌉>1. We conjecture this bound is almost tight when L+1=ℓa for any a∈ℕ≥ 2. To give some evidences, we show folded RS codes over the alphabet Fqs are (1/2−sR/s−2,2,3) list-recoverable, which proves the tightness of this bound in the smallest non-trivial special case. As a corollary, our bound states (folded) RS codes cannot be (1−R−є, ℓ, ℓoR(1/є)) list-recoverable, which refutes the possibility that these codes could achieve list-recovery capacity (1−R−є, ℓ, O(ℓ/є)). This implies an intrinsic separation between list-decodability and list-recoverablility of (folded) RS codes.