Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
arXiv:2609.08005
Abstract
We give a deterministic polynomial-time list-decoding algorithm for Reed-Solomon codes over prime fields that approaches list-decoding capacity for every evaluation set and every constant rate.
27 pages. We are grateful to Omar Alrabiah, Rohan Goyal, and Venkat Guruswami for sharing their padding observation with us, which enabled us to extend our results from low constant rate to all rates