Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets

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 0 and R (0, 1), with high probability, randomly punctured Reed-Solomon codes of block length n and rate R are (1-R-, O (1 /) ) list decodable over alphabets of size at least 2^ {poly (1 /) } 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).