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-\epsilon$ with list size at most $\frac{1-R-\epsilon}{\epsilon}$, resolving a conjecture of Shangguan and Tamo.

翻译：在最近的一篇论文中，Brakensiek，Gopi和Makam将高阶MDS码作为MDS码的一般化。 $\ell$阶MDS码，表示为$\operatorname{MDS}(\ell)$，具有的性质是其生成矩阵的任意$\ell$个形成的子空间之间的交集尽可能小。 Roth提出的独立作品则定义了另一种高阶MDS码的概念，即那些实现列表译码的广义单例限。在这项工作中，我们表明这两种高阶MDS码的概念是（近乎）等价的。我们还表明，通用Reed-Solomon码对于所有$\ell$都是$\operatorname{MDS}(\ell)$，具有GM-MDS定理的关键作用，该定理表明，通用Reed-Solomon码的生成矩阵实现任何可能的零模式。作为推论，这意味着通用Reed-Solomon码实现列表译码容量。更具体地说，我们表明，在指数级别的大字段上，比率为R的随机Reed-Solomon码在半径为$1-R-\epsilon$时可以被有高概率列表译码，列表大小最多为$\frac{1-R-\epsilon}{\epsilon}$，解决了Shangguan和Tamo的一个猜想。