Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
Zeyu Guo, Zihan Zhang · 2023
This paper shows that, with high probability, randomly punctured Reed-Solomon codes over fields of polynomial size achieve the list decoding capacity. More specifically, we prove that for any $\varepsilon \gt 0$ and $R \in(0,1)$, with high probability, randomly punctured Reed-Solomon codes of block length n and rate R are $(1-R-\varepsilon, O(1 / \varepsilon))$ list decodable over alphabets of size at least $2^{\text {poly }(1 / \varepsilon)} n^{2}$. This extends the recent breakthrough of Brakensiek, Gopi, and Makam (STOC 2023) that randomly punctured Reed-Solomon codes over fields of exponential size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020).