Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908815116468224 |
|---|---|
| author | Brakensiek, Joshua Dhar, Manik Gopi, Sivakanth |
| author_facet | Brakensiek, Joshua Dhar, Manik Gopi, Sivakanth |
| contents | In this paper, we continue the study of Maximally Recoverable (MR) Grid Codes initiated by Gopalan et al. [SODA 2017]. More precisely, we study codes over an $m \times n$ grid topology with one parity check per row and column of the grid along with $h \ge 1$ global parity checks. Previous works have largely focused on the setting in which $m = n$, where explicit constructions require field size which is exponential in $n$. Motivated by practical applications, we consider the regime in which $m,h$ are constants and $n$ is growing. In this setting, we provide a number of new explicit constructions whose field size is polynomial in $n$. We further complement these results with new field size lower bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15013 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes Brakensiek, Joshua Dhar, Manik Gopi, Sivakanth Information Theory In this paper, we continue the study of Maximally Recoverable (MR) Grid Codes initiated by Gopalan et al. [SODA 2017]. More precisely, we study codes over an $m \times n$ grid topology with one parity check per row and column of the grid along with $h \ge 1$ global parity checks. Previous works have largely focused on the setting in which $m = n$, where explicit constructions require field size which is exponential in $n$. Motivated by practical applications, we consider the regime in which $m,h$ are constants and $n$ is growing. In this setting, we provide a number of new explicit constructions whose field size is polynomial in $n$. We further complement these results with new field size lower bounds. |
| title | Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2509.15013 |