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

In this paper, we prove that any `appropriate' folded Reed-Solomon and univariate multiplicity codes achieve relaxed generalized Singleton bound for list size L≥1. More concretely, we show the following: (1) Any (s,γ)-folded RS code over the alphabet Fqˢ of block length n and rate R with pair-wise distinct evaluation points \γⁱαⱼ_(i,j)∈(\0\[s-1],[n])q are (L/L+1(1-sR/s-L+1),L) (average-radius) list-decodable for list size L∈[s]. (2) Any s-order univariate multiplicity code over the alphabet Fₚˢ (p is a prime) of block length n and rate R with pair-wise distinct evaluation points \αᵢ∈[n]ₚ are (L/L+1(1-sR/s-L+1),L) (average-radius) list-decodable for list size L∈[s]. Choose s=Θ(1/ε²) 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 evidently optimal list size O(1/ε), which 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.