Improved Field Size Bounds for Higher Order MDS Codes
Improved Field Size Bounds for Higher Order MDS Codes
复制标题
DOI：
10.1109/isit54713.2023.10206952
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Joshua Brakensiek;Manik Dhar;Sivakanth Gopi
中科院分区：
文献类型：
--
作者：
Joshua Brakensiek;Manik Dhar;Sivakanth Gopi
高阶MDS码是最近由Brakensiek、Gopi和Makam（IEEE Trans. Inf. Theory 2022）引入的MDS码的有趣推广。在后来的工作中，它们被证明与最优列表可解码码和最大可恢复张量码密切相关。因此，小域上高阶MDS码的（显式）构造是一个重要的公开问题。高阶MDS码用MDS（2）表示，其中MDS（2）表示一般性阶，MDS（2）码等价于通常的MDS码。（n，k）-MDS（n）码的域大小的最佳先验下界是N（nk（nk-1）），而最好的（非显式）上界是O（nk（nk（nk-1）），它在维数上是指数的。在这项工作中，我们几乎关闭了上界和下界之间的指数差距。我们证明了一个（n，k）-MDS（3）码需要一个大小为nk（nk−1）的域，这接近于已知的上界。利用高阶MDS码与最优列表可译码码之间的联系，我们证明了即使列表大小为2，满足最优列表译码Singleton界的码也需要指数域大小;这解决了上官和塔莫的一个悬而未决的问题，（STOC 2020）。我们还给出了大小为${n^{（\ell k）}^{O（\ell k）}$的域上的（n，k）-MDS（MDS）码的显式构造。我们仍然没有最优构造的最小非平凡情况是（n，3）-MDS（3）。在这种情况下，已知的字段大小的下限是O（n2），最好的已知上限是O（n5）（对于非显式构造）和O（n32）（对于显式构造）。在本文中，我们给出了一个明确的建设领域的大小为O（n3），这是非常接近最优的。
Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek, Gopi and Makam (IEEE Trans. Inf. Theory 2022). In later works, they were shown to be intimately connected to optimally list-decodable codes and maximally recoverable tensor codes. Therefore (explicit) constructions of higher order MDS codes over small fields is an important open problem. Higher order MDS codes are denoted by MDS(ℓ) where ℓ denotes the order of generality, MDS(2) codes are equivalent to the usual MDS codes. The best prior lower bound on the field size of an (n, k)-MDS(ℓ) codes is Ωℓ(nℓ−1), whereas the best known (non-explicit) upper bound is Oℓ(nk(ℓ−1)) which is exponential in the dimension.In this work, we nearly close this exponential gap between upper and lower bounds. We show that an (n, k)-MDS(3) codes requires a field of size Ωk(nk−1), which is close to the known upper bound. Using the connection between higher order MDS codes and optimally list-decodable codes, we show that even for a list size of 2, a code which meets the optimal list-decoding Singleton bound requires exponential field size; this resolves an open question from Shangguan and Tamo (STOC 2020).We also give explicit constructions of (n, k)-MDS(ℓ) code over fields of size ${n^{{{(\ell k)}^{O(\ell k)}}}}$. The smallest non-trivial case where we still do not have optimal constructions is (n, 3)-MDS(3). In this case, the known lower bound on the field size is Ω(n2) and the best known upper bounds are O(n5) for a non-explicit construction and O(n32) for an explicit construction. In this paper, we give an explicit construction over fields of size O(n3) which comes very close to being optimal.