Papers › Improved Field Size Bounds for Higher Order MDS Codes
Improved Field Size Bounds for Higher Order MDS Codes
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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_ℓ(n^(k(ℓ-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 Ωₖ(nᵏ⁻¹), 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 / SIAM J. on Computing 2023). We also give explicit constructions of (n,k)-MDS(ℓ) code over fields of size n^((ℓk)^(O(ℓ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 Ω(n²) and the best known upper bounds are O(n⁵) for a non-explicit construction and O(n³²) for an explicit construction. In this paper, we give an explicit construction over fields of size O(n³) which comes very close to being optimal.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections