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

04/03/2023

∙

by   Zeyu Guo, et al.

∙

0

∙

share

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).