PreprintCC BY 4.0arXiv
Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
Abstract
Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to solve the proximity-gaps question for RS codes. In this article, we give a unified and transparent exposition of these results.
Related
- Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Combinatorial limitations of list-decoding Reed-Solomon codes
- MacKay-Neal Codes Achieve Capacity under MAP Decoding
- Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound
BibTeX
@misc{harsha2026reedsolomon,
title = {{Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps}},
author = {Prahladh Harsha and Mrinal Kumar and Ramprasad Saptharishi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08610},
eprint = {2610.08610},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08610},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
AU - Prahladh Harsha
AU - Mrinal Kumar
AU - Ramprasad Saptharishi
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08610
UR - https://arxiv.org/abs/2610.08610
AB - Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to solve the proximity-gaps question for RS codes. In this article, we give a unified and transparent exposition of these results.
ER -