An Improved Johnson Bound for List-Decoding with Hints
Abstract
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 δ is automatically list-decodable with small list size up to a certain radius J(δ) 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(δ)−ε)-close to r improves the list-decoding radius around r to J(δ)+ε'. Finally, we give an efficient algorithm, based on the weighted Guruswami-Sudan decoder, that list-decodes Reed-Solomon codes up to this optimal radius.
Related
- A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
- A polylogarithmic bound for list replicability
BibTeX
@misc{kopparty2026improved,
title = {{An Improved Johnson Bound for List-Decoding with Hints}},
author = {Swastik Kopparty and Harry Sha},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38022},
eprint = {2610.38022},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38022},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - An Improved Johnson Bound for List-Decoding with Hints
AU - Swastik Kopparty
AU - Harry Sha
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.38022
UR - https://arxiv.org/abs/2610.38022
AB - 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 δ is automatically list-decodable with small list size up to a certain radius J(δ) 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(δ)−ε)-close to r improves the list-decoding radius around r to J(δ)+ε'. Finally, we give an efficient algorithm, based on the weighted Guruswami-Sudan decoder, that list-decodes Reed-Solomon codes up to this optimal radius.
ER -