Algorithmic List Decoding of Reed-Solomon Codes up to Capacity

Scientific Impact Assessment

Core Contribution. This paper resolves a central, three-decade-old open problem in coding theory: whether Reed–Solomon (RS) codes can be *efficiently* list-decoded beyond the Johnson radius (1−√R). The authors give a deterministic polynomial-time algorithm that list-decodes RS codes over prime fields all the way up to list-decoding capacity (1−R−ε) for *arbitrary* evaluation sets and any constant rate, with polynomial list size. This is not merely an incremental improvement over Guruswami–Sudan (1999); it breaks a barrier that the community had strong reason to believe might be fundamental — prior work (Ben-Sasson–Kopparty–Radhakrishnan, Guruswami–Rudra, Cheng–Wan) established combinatorial and computational-hardness obstructions to decoding substantially beyond Johnson. Strikingly, even an *explicit combinatorial* bound beyond Johnson for RS codes was previously unknown; this work delivers both the combinatorial and algorithmic result simultaneously.

Methodological Rigor. The technical heart is a genuinely new interpolation idea: augment the Sudan/Guruswami–Sudan interpolate-and-root-find template by introducing *Hasse derivatives* of the unknown message polynomial as additional formal variables, even though the decoder has no derivative information. The key insight is that candidate derivative tuples are not arbitrary — they satisfy a backward Taylor/Möbius relation — so the interpolation constraints can be substantially reduced via a clever substitution, defeating the rate-inefficiency (A > √(nk)) that pins Guruswami–Sudan to Johnson. The proofs are detailed and self-contained: careful weighted lattice-point/simplex-volume counting bounds the constraint rank, and root-finding is reduced cleanly to Kopparty's univariate-multiplicity decoder as a black box. The derivations appear sound and the counting arguments are explicit. Minor caveats: the exposition contains typos ("lenght," "Gurusawmi"), and the all-rates extension relies on an externally supplied reduction (credited to Alrabiah–Goyal–Guruswami) plus a promised white-box argument "documented in a future version" — so the cleanest full-generality statement is partly deferred.

Potential Impact. RS codes are foundational across data storage, communication, cryptography, and — increasingly — succinct/interactive proof systems (STIR, WHIR, FRI, proximity testing), where RS proximity and decoding radius directly affect soundness parameters. List decoding also underpins pseudorandomness, hardness amplification, and randomness extraction. A capacity-achieving *efficient* algorithm for the canonical RS code (rather than folded RS or multiplicity codes, which require larger alphabets or structural modifications) is a conceptual landmark that will be heavily cited and built upon. The paper already reports contemporaneous follow-ups extending the technique white-box to all rates, signaling immediate foundational reuse. Practically, however, deployment is limited: the list size and runtime carry exponents polynomial in 1/ε with unfavorable dependence (q^{O(ε^{-12/θ})} runtime), and the result requires field size Θ(n) and prime fields, so this is primarily a theoretical breakthrough rather than an immediately deployable decoder.

Timeliness & Relevance. Extremely timely. There has been a recent surge of activity on RS list-decodability (random puncturing achieving capacity combinatorially, generalized Singleton bound, folded-RS list-size improvements). The efficient/explicit gap was the glaring remaining bottleneck, repeatedly flagged as the open question "dating back to Guruswami–Sudan." This paper closes exactly that gap. The origin story — inspired by a crowd-sourced Proximity Prize submission and developed with GPT-5 assistance (with authors taking responsibility for verification) — is itself a notable data point about emerging research workflows.

Strengths & Limitations. Strengths: (1) resolves a marquee open problem; (2) a conceptually clean and reusable new interpolation primitive; (3) works for *worst-case* evaluation sets deterministically, unlike the random-evaluation-point line of work; (4) unifies combinatorial and algorithmic progress. Limitations: (1) restricted to prime fields and constant rate in the self-contained portion; (2) large runtime/list-size exponents preclude practical use; (3) field size Θ(n) rather than the ideal near-linear/small-alphabet regime; (4) the fully general all-rates white-box proof is deferred; (5) it does not achieve the optimal (generalized Singleton) list size for fixed list size, which random-RS results attain. These are refinements the follow-up literature will surely pursue.

Additional observations. The work is purely theoretical (pen-and-paper, no compute barrier), so reproducibility rests on the completeness of the proofs and pseudocode, both of which are provided. The refutation angle is meaningful but nuanced: the prior obstruction results were for bounded-characteristic fields and specific regimes, so this paper does not contradict them; rather it demonstrates that Johnson is *not* a fundamental algorithmic barrier for prime fields, correcting a widely-held pessimistic expectation without overturning a formal theorem.

Overall, this is a top-tier, likely award-caliber theoretical contribution whose main risk factors are the unusual provenance and the deferred full-generality proof — both of which warrant independent verification but do not diminish the apparent correctness and importance of the core result.