An Improved Johnson Bound for List-Decoding with Hints
cs.IT, math.IT
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: 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…
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 papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Electromagnetic Signal and Information Theory: A Continuous-Aperture Array Perspective
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound