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).
Joint work with Zihan Zhang. FOCS 23. arxiv.org/abs/2304.01403 .
