Metraipolis › archive › dc_cde1417f99da

An Improved Johnson Bound for List-Decoding with Hints — arXiv:2610.38022

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.38022
License (as archived)
CC0-1.0
Archived
2026-11-01T02:39:38.246Z
SHA-256 of the archived text
382755235e3449b20a64eafb403181a10e31be878b15fc76b5fd16b4069b8b27
Stable URL of this page
https://metraipolis.com/documento/dc_cde1417f99da

How to cite

An Improved Johnson Bound for List-Decoding with Hints — arXiv:2610.38022 — arXiv (en), https://arxiv.org/abs/2610.38022 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cde1417f99da (Metraipolis archive dc_cde1417f99da, sha256 382755235e3449b20a64eafb403181a10e31be878b15fc76b5fd16b4069b8b27)
BibTeX
@misc{dccde1417f99da,
  title = {An Improved Johnson Bound for List-Decoding with Hints — arXiv:2610.38022},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.38022},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cde1417f99da; sha256 382755235e3449b20a64eafb403181a10e31be878b15fc76b5fd16b4069b8b27},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38022. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

This paper studies when list-decodability guarantees for error-correcting codes of good distance can go beyond the classical Johnson radius and gives a corresponding efficient list-decoding algorithm for Reed-Solomon codes up to this new radius. The Johnson bound shows that any error-correcting code with distance $\delta$ is automatically list-decodable with small list size up to a certain radius $J(\delta)$ around any received word $r$. We show that if the received word $r$ is known to have some codewords that are somewhat close to it (we call these ``hints"), then $C$ is list-decodable with small list size up to an even larger radius around $r$. We determine the optimal list-decoding radius in this setting for single and multiple hints over both large and small alphabets and show that this radius is the optimum of a natural convex program. Remarkably, even a single hint that is $(J(\delta)-\epsilon)$-close to $r$ improves the list-decoding radius around $r$ to $J(\delta)+\epsilon'$. Finally, we give an efficient algorithm, based on the weighted Guruswami-Sudan decoder, that list-decodes Reed-Solomon codes up to this optimal radius.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.38022 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:43.718Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).