Let's Have Both! Optimal List-Recoverability via Alphabet Permutation 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_ | 1866908355242491904 |
|---|---|
| author | Komech, Sergey Mosheiff, Jonathan |
| author_facet | Komech, Sergey Mosheiff, Jonathan |
| contents | We introduce alphabet-permutation (AP) codes, a new family of error-correcting codes defined by iteratively applying random coordinate-wise permutations to a fixed initial word. A special case recovers random additive codes and random binary linear codes, where each permutation corresponds to an additive shift over a finite field.
We show that when these permutations are drawn from a suitably ``mixing'' distribution, the resulting code is almost surely list-recoverable with list size proportional to the inverse of the gap to capacity. Compared to any linear code, our construction achieves exponentially smaller list sizes at the same rate. Previously, only fully random codes were known to attain such parameters, requiring exponentially many random bits and offering no structure. In contrast, AP codes are structured and require only polynomially many random bits -- providing the first such construction to match the list-recovery guarantees of random codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05858 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Let's Have Both! Optimal List-Recoverability via Alphabet Permutation Codes Komech, Sergey Mosheiff, Jonathan Information Theory We introduce alphabet-permutation (AP) codes, a new family of error-correcting codes defined by iteratively applying random coordinate-wise permutations to a fixed initial word. A special case recovers random additive codes and random binary linear codes, where each permutation corresponds to an additive shift over a finite field. We show that when these permutations are drawn from a suitably ``mixing'' distribution, the resulting code is almost surely list-recoverable with list size proportional to the inverse of the gap to capacity. Compared to any linear code, our construction achieves exponentially smaller list sizes at the same rate. Previously, only fully random codes were known to attain such parameters, requiring exponentially many random bits and offering no structure. In contrast, AP codes are structured and require only polynomially many random bits -- providing the first such construction to match the list-recovery guarantees of random codes. |
| title | Let's Have Both! Optimal List-Recoverability via Alphabet Permutation Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2502.05858 |