


























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。