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 $\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 }^{\prime }$. Finally, we give an efficient algorithm, based on the weighted Guruswami-Sudan decoder, that list-decodes Reed-Solomon codes up to this optimal radius.