Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914016166674432 |
|---|---|
| author | Guo, Zeyu Zhang, Zihan |
| author_facet | Guo, Zeyu Zhang, Zihan |
| contents | This paper shows that, with high probability, randomly punctured Reed-Solomon codes over fields of polynomial size achieve the list decoding capacity. More specifically, we prove that for any $ε>0$ and $R\in (0,1)$, with high probability, randomly punctured Reed-Solomon codes of block length $n$ and rate $R$ are $\left(1-R-ε, O({1}/ε)\right)$ list decodable over alphabets of size at least $2^{\mathrm{poly}(1/ε)}n^2$. This extends the recent breakthrough of Brakensiek, Gopi, and Makam (STOC 2023) that randomly punctured Reed-Solomon codes over fields of exponential size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_01403 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets Guo, Zeyu Zhang, Zihan Information Theory Data Structures and Algorithms Combinatorics This paper shows that, with high probability, randomly punctured Reed-Solomon codes over fields of polynomial size achieve the list decoding capacity. More specifically, we prove that for any $ε>0$ and $R\in (0,1)$, with high probability, randomly punctured Reed-Solomon codes of block length $n$ and rate $R$ are $\left(1-R-ε, O({1}/ε)\right)$ list decodable over alphabets of size at least $2^{\mathrm{poly}(1/ε)}n^2$. This extends the recent breakthrough of Brakensiek, Gopi, and Makam (STOC 2023) that randomly punctured Reed-Solomon codes over fields of exponential size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020). |
| title | Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets |
| topic | Information Theory Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2304.01403 |