Paper 2026/2048

Linear list size bounds for Reed-Solomon beyond the Johnson radius

Abstract

Based on techniques discovered in the better.codes autoresearch project, we show that Reed-Solomon codes of rate $\rho$ and block length $n$ over a field of sufficiently large characteristic, have $C\cdot n$ list size bound when requiring fractional agreement $\alpha$ with a received word; where $C,\alpha$ are constants depending only on $\rho$ and $\alpha<\sqrt{\rho}$. This complements the recent breakthrough results [BCPZZ26,Jeronimo26] achieving $n^c$ list size bounds with agreement $\rho+\epsilon$ for any constant $\epsilon>0$ with an unspecified constant exponent $c$.