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

67 SixSeven Mini App: Mapping a Wallet-to-Card User Flow Without an API
0dev.to Design
413 files, 1 badge: I re-ran Anthropic's memory test
0dev.to Discuss
Building Astrodios: A Daily Reading as a Prompt, Not a Prediction — What Worked, What Broke
0dev.to Discuss
Your AI doesn't know your project as well as you think.
0dev.to Discuss
Maybe developers don't need more AI. Maybe they need less friction.
0dev.to Productivity

Trust Network - An Agent-to-Agent Communication Protocol built on top of Switch
0dev.to Productivity