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 L1. 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 \ⁱⱼ\ (₈, ₉) (\₀\-1, n) q are (LL+1 (1-sRs-L+1), L) (average-radius) list-decodable for list size L. (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 \ᵢ\₈ₚ are (LL+1 (1-sRs-L+1), L) (average-radius) list-decodable for list size L. 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.