Backend
Combinatorial limitations of list-decoding Reed-Solomon codes
arXiv math.IT0 views
arXiv:2611.07607v1 Announce Type: new 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.
Source：https://arxiv.org/abs/2611.07607PreviousInformation-Spectrum General Formulas for the Capacity Region of Classical-Quantum Multiple Access ChannelsNextA Universal Threshold Theory for Local Properties of Random Linear Codes
Related posts
Checking eSIM Device Compatibility Before Checkout: What You Can and Can't Detect
0dev.to
Allow, Ask, or Block: The Week Agent Security Moved to the Action
0dev.to
Incremental Dependency-Graph Recalculation for 184 Excel Formulas in a Browser Web Worker
0dev.to
How to add an even white border and cut line to a sticker design
0dev.to Design
Building WUUUH: Turning a Resume Gap Into a Story, Not an Apology — What Worked, What Broke
0dev.to Discuss
From HackerTube to Amblyotube: When Community Curation Meets Vision Training
0dev.to Discuss