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

Abstract

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

This paper has been withdrawn by the authors. It has been superseded by arXiv:2304.09445, the merged journal version of arXiv:2304.09445v5 and arXiv:2304.01403v2