PreprintCC BY 4.0arXiv
Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
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.
Related
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
- Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes
- Combinatorial limitations of list-decoding Reed-Solomon codes
- Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
BibTeX
@misc{brakensiek2026algorithmic,
title = {{Algorithmic List Decoding of Reed-Solomon Codes up to Capacity}},
author = {Joshua Brakensiek and Yeyuan Chen and Aaron Putterman and Zihan Zhang and Kai Zhe Zheng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08005},
eprint = {2609.08005},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08005},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
AU - Joshua Brakensiek
AU - Yeyuan Chen
AU - Aaron Putterman
AU - Zihan Zhang
AU - Kai Zhe Zheng
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.08005
UR - https://arxiv.org/abs/2609.08005
AB - 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.
ER -