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

How I Discovered a Leak Exposing 1,000+ Customer Emails via a Simple API Query (?select=*)
0dev.to
bolt.diy scans need a workspace and provider-key review
0dev.to
Let the LLM group, let code count: pain points across a dozen RedNote, Douyin and YouTube posts (and what broke on the first live run)
0dev.to

How I Contributed 5 Integrations to Switch During the Flip the Switch Hackathon
0dev.to
Ecoflow Rapid Pro Power Bank Deal: Save $80
0Wired

# Connecting Signal with AI Agents: My Open-Source Contribution to Switch
0dev.to