arXiv preprint ·
Combinatorial limitations of list-decoding Reed-Solomon codes
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate $R$ with polynomially many codewords in a Hamming ball of relative radius bounded strictly below $1-R$. This refutes a recent conjecture that, over prime fields, list sizes below capacity are always bounded by a constant. Together, these results demonstrate that certain restrictions in recent works on explicit Reed-Solomon codes achieving list-decoding capacity, related to the choice of field or evaluation points or to the list-size guarantee, are inherent.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Asymptotic advantage of quantum one-way and SMP communication for total functions
Structured Quantum Hardness from Unstructured Assumptions
A Universal Threshold Theory for Local Properties of Random Linear Codes
Randomized Parallel Complexity of Weakly Convex Optimization
Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.