Papers for

coding theory tool developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Reed-Solomon codes show superpolynomial list sizes over binary extensions

Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields

Abstract: Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate $0<R<1$, there exists $\varepsilon_R>0$ such that, for all sufficiently large $h$, the full-field Reed--Solomon code over $\mathbb{F}_{2^h}$ has a received word with $n^{Ω_R(\log n)}$ codewords within relative distance $1-R-\varepsilon_R$. To our knowledge, these are the first superpolynomial ordinary Reed--Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed--Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed--Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose--Chaudhuri--Hocquenghem weight-enumerator coefficients into sizes of single Reed--Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.

Sun 11 OctInformation TheoryComputational Complexity
The gist
Reed-Solomon codes are widely used for correcting errors in data. Normally, for codes over prime number fields, the number of possible close matches stays manageable when decoding. This paper finds that for codes over binary extension fields, there can be an extremely large, superpolynomial number of close matches, making decoding much harder. The authors demonstrate this phenomenon happens at all fixed data rates and persist even when the code is modified slightly. This result challenges assumptions about decoding efficiency depending on the underlying field.
Open → 2610.15815v1