论文标题
通用的芦苇 - 固体代码实现了列表编码能力
Generic Reed-Solomon Codes Achieve List-decoding Capacity
论文作者
论文摘要
在最近的一篇论文中，Brakensiek，Gopi和Makam引入了高阶MDS代码作为MDS代码的概括。订单 - $ \ ell $ mds代码，由$ \ permatatorName {mds}（\ ell）$表示，具有从其生成器矩阵的列形成的任何$ \ ell $ subspaces的属性，尽可能最小。罗斯（Roth）的独立工作将高阶MDS代码的不同概念定义为那些实现列出列表编码的广义单例的概念。在这项工作中，我们表明，这两个高阶MDS代码的概念几乎是（几乎）等效的。 我们还表明，对于所有$ \ ell $，通用的芦苇 - 固体代码是$ \ operatotorname {mds}（\ ell）$，依赖于GM-MDS定理，它表明，通用的Reed-Solomon代码的生成矩阵实现了任何可能的零模式。作为推论，这意味着通用的芦苇 - 固体代码可实现列表解码能力。更具体地说，我们表明，凭借高概率，在呈指数级的大字段上，随机的REED - 固体代码$ r $ $ r $是可以从RADIUS $ 1-R-ε$解码的，最多最多$ \ frac {1-R-ε}ε$，从而解决了Shangguan和Tamo的猜想。
In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-$\ell$ MDS code, denoted by $\operatorname{MDS}(\ell)$, has the property that any $\ell$ subspaces formed from columns of its generator matrix intersect as minimally as possible. An independent work by Roth defined a different notion of higher order MDS codes as those achieving a generalized singleton bound for list-decoding. In this work, we show that these two notions of higher order MDS codes are (nearly) equivalent. We also show that generic Reed-Solomon codes are $\operatorname{MDS}(\ell)$ for all $\ell$, relying crucially on the GM-MDS theorem which shows that generator matrices of generic Reed-Solomon codes achieve any possible zero pattern. As a corollary, this implies that generic Reed-Solomon codes achieve list decoding capacity. More concretely, we show that, with high probability, a random Reed-Solomon code of rate $R$ over an exponentially large field is list decodable from radius $1-R-ε$ with list size at most $\frac{1-R-ε}ε$, resolving a conjecture of Shangguan and Tamo.
