Generalized GM-MDS: Polynomial Codes are Higher Order MDS
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913873195433984 |
|---|---|
| author | Brakensiek, Joshua Dhar, Manik Gopi, Sivakanth |
| author_facet | Brakensiek, Joshua Dhar, Manik Gopi, Sivakanth |
| contents | The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible configuration of zeros for an MDS code. The recently emerging theory of higher order MDS codes has connected the GM-MDS theorem to other important properties of Reed-Solomon codes, including showing that Reed-Solomon codes can achieve list decoding capacity, even over fields of size linear in the message length.
A few works have extended the GM-MDS theorem to other families of codes, including Gabidulin and skew polynomial codes. In this paper, we generalize all these previous results by showing that the GM-MDS theorem applies to any polynomial code, i.e., a code where the columns of the generator matrix are obtained by evaluating linearly independent polynomials at different points. We also show that the GM-MDS theorem applies to dual codes of such polynomial codes, which is non-trivial since the dual of a polynomial code may not be a polynomial code. More generally, we show that GM-MDS theorem also holds for algebraic codes (and their duals) where columns of the generator matrix are chosen to be points on some irreducible variety which is not contained in a hyperplane through the origin. Our generalization has applications to constructing capacity-achieving list-decodable codes as shown in a follow-up work by Brakensiek-Dhar-Gopi-Zhang, where it is proved that randomly punctured algebraic-geometric (AG) codes achieve list-decoding capacity over constant-sized fields. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_12888 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Generalized GM-MDS: Polynomial Codes are Higher Order MDS Brakensiek, Joshua Dhar, Manik Gopi, Sivakanth Information Theory Algebraic Geometry Combinatorics The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible configuration of zeros for an MDS code. The recently emerging theory of higher order MDS codes has connected the GM-MDS theorem to other important properties of Reed-Solomon codes, including showing that Reed-Solomon codes can achieve list decoding capacity, even over fields of size linear in the message length. A few works have extended the GM-MDS theorem to other families of codes, including Gabidulin and skew polynomial codes. In this paper, we generalize all these previous results by showing that the GM-MDS theorem applies to any polynomial code, i.e., a code where the columns of the generator matrix are obtained by evaluating linearly independent polynomials at different points. We also show that the GM-MDS theorem applies to dual codes of such polynomial codes, which is non-trivial since the dual of a polynomial code may not be a polynomial code. More generally, we show that GM-MDS theorem also holds for algebraic codes (and their duals) where columns of the generator matrix are chosen to be points on some irreducible variety which is not contained in a hyperplane through the origin. Our generalization has applications to constructing capacity-achieving list-decodable codes as shown in a follow-up work by Brakensiek-Dhar-Gopi-Zhang, where it is proved that randomly punctured algebraic-geometric (AG) codes achieve list-decoding capacity over constant-sized fields. |
| title | Generalized GM-MDS: Polynomial Codes are Higher Order MDS |
| topic | Information Theory Algebraic Geometry Combinatorics |
| url | https://arxiv.org/abs/2310.12888 |