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 $\epsilon>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-\epsilon, O({1}/{\epsilon})\right)$ list decodable over alphabets of size at least $2^{\mathrm{poly}(1/\epsilon)}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).
翻译:本文证明,在高概率情况下,对于任何$\epsilon>0$和$R\in(0,1)$,随机删减的Reed-Solomon码在多项式大小字母上,可以以概率上界容忍$\left(1-R-\epsilon,O({1}/{\epsilon})\right)$的列表解码错误,其中码长为$n$,速率为$R$。这扩展了Brakensiek、Gopi和Makam(STOC 2023)最近的突破,他们证明随机删减的Reed-Solomon码在指数大小的有限域上达到了Shangguan和Tamo(STOC 2020)的广义Singleton界。此外,Alon和Berman(IEEE Trans. Inform. Theory,2016)的思想是我们证明新结果的主要工具,他们使用随机生成的码字,以接近容量的概率表现良好。