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)的思想是我们证明新结果的主要工具,他们使用随机生成的码字,以接近容量的概率表现良好。

0
下载
关闭预览

相关内容

【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
专知会员服务
31+阅读 · 2021年7月15日
专知会员服务
88+阅读 · 2021年6月29日
【普林斯顿大学-微软】加权元学习,Weighted Meta-Learning
专知会员服务
39+阅读 · 2020年3月25日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
DeepMind开源最牛无监督学习BigBiGAN预训练模型
新智元
10+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
后ResNet时代:SENet与SKNet
PaperWeekly
23+阅读 · 2019年3月25日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年5月23日
Arxiv
0+阅读 · 2023年5月23日
Arxiv
0+阅读 · 2023年5月18日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
DeepMind开源最牛无监督学习BigBiGAN预训练模型
新智元
10+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
后ResNet时代:SENet与SKNet
PaperWeekly
23+阅读 · 2019年3月25日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员