PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithmic List Decoding of Reed-Solomon Codes up to Capacity

Joshua Brakensiek, Yeyuan Chen, Aaron Putterman, Zihan Zhang, Kai Zhe Zheng

arXiv:2609.08005v1cs.ITcs.CCmath.IT

TL;DR

Efficient Reed–Solomon list decoding has been known up to the Johnson radius, below capacity. This paper uses structured interpolation constraints involving higher derivatives, with root-finding to recover candidate messages. It gives capacity decoding for arbitrary evaluation sets over prime fields at constant rates, while noting that its all-rate extension uses a black-box reduction.

  • Problem

    Efficient Reed–Solomon list decoding was known up to the Johnson radius, leaving a gap to list-decoding capacity.

    Source: §1 · pp. 2–3

  • Method

    The algorithm interpolates using formal variables for higher derivatives under structured constraints, then applies root-finding to recover candidate message polynomials.

    Source: §1.1 · pp. 4–5

  • Results

    The algorithm reaches list-decoding capacity for arbitrary evaluation sets over prime fields at every constant rate.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The paper gives an efficient capacity-decoding result for Reed–Solomon codes without requiring random evaluation points.

    Source: §1 · p. 3

    The all-rate extension in this version uses a black-box reduction; white-box modifications are deferred to a future version.

    Source: §1 · p. 3

Abstract

from arXiv · show

We give a deterministic polynomial-time list-decoding algorithm for Reed-Solomon codes over prime fields that approaches list-decoding capacity for every evaluation set and every constant rate.

1 Introduction

The paper closes the gap between efficient Reed–Solomon list decoding and capacity over prime fields, including arbitrary evaluation sets and constant rates. Its key technique uses structured constraints on higher derivatives to construct an interpolant, then finds candidate polynomials by root-finding.

1 Introduction

  • The introduction frames the question against Reed–Solomon codes’ role in error correction and their applications in storage, wireless communication, and cryptography.List decoding seeks nearby codewords beyond unique decoding and has applications across theoretical computer science.Source: §1 · pp. 1–2
  • The open gap was between the Johnson-radius algorithms and the list-decoding capacity 1−R, despite capacity results for random evaluation points.Those random-point results were combinatorial and did not provide efficient decoding; no explicit RS family had comparable combinatorial guarantees.Source: §1 · p. 2
  • For θ∈(0,1) and 0<ε<ε₀(θ), sufficiently low but constant-rate Reed–Solomon codes with arbitrary distinct evaluation points over prime fields of size q = Θ_{θ,ε}(n) decode up to 1−ε errors with list size n^poly_θ(1/ε).Source: §1 · p. 3
  • The all-rate extension gives capacity decoding for arbitrary evaluation sets over prime fields, with output list size n^O_R,δ(1).The informal corollary applies to codes of rate at most R when the prime field has size at least Cn.Source: §1 · p. 3
  • The all-rate result in this version uses a black-box reduction; contemporaneous white-box modifications are deferred to a future manuscript.The authors say those modifications achieve capacity at all constant rates.Source: §1 · p. 3

1.1 Origins of the Main Ideas and Technique Overview

  • The decoder interpolates with formal variables for the message polynomial’s Hasse derivatives, then uses a univariate multiplicity decoder to find candidates.It verifies each recovered polynomial has the target agreement with the received word.Source: §1.1 · p. 4
  • Backward Taylor structure restricts the interpolation constraints to derivative tuples consistent with the received value, avoiding the naive system’s lack of a guaranteed nonzero solution.The method bounds constraint-map rank by finding a large-dimensional kernel subspace and using weighted lattice-point counting.Source: §1.1 · pp. 5–6

2 Preliminaries

The preliminaries set the prime-field setting, introduce Hasse derivatives and weighted degree, and state a root-finding result used by the decoding approach.

2 Preliminaries

  • The preliminaries define Hasse derivatives and derive a Möbius-inversion identity that the interpolation uses.Source: §2 · p. 7
  • Weighted degree is the maximum weight-sum of a monomial’s exponents, with degree in one variable as a special case.Source: §2 · p. 7
  • Kopparty’s result finds all qualifying low-degree polynomials in q^O(d+1) time when q is prime and exceeds the polynomial’s relevant weighted degrees.The number found is at most q^(4d+6).Source: §2 · pp. 6–7

3 Novel Interpolation via Hidden Derivatives

The section develops a hidden-derivative interpolation method, using an explainer polynomial to encode candidate-polynomial derivatives and a structured interpolation space. It bounds the independent constraints and shows that, under stated conditions, a nonzero interpolation polynomial vanishes on the derivative-evaluation data of every sufficiently agreeing codeword polynomial.

3 Novel Interpolation via Hidden Derivatives

  • Local constraints encode unknown candidate derivatives through formal variables and a remainder, ensuring multiplicity at each received point for a candidate that agrees there.The polynomial’s derivatives are unavailable during interpolation, but any candidate passing through the received point must satisfy the formal relation used in the substitution.Source: §3 · pp. 8–9

3.1 Dimension of the Interpolation Space

  • The interpolation space uses monomials filtered by ordinary and weighted degree for Y2 through Yd, with a separate degree restriction on Y1.The weight assigned to Yj is j−1, reflecting the powers of T accompanying the successive derivatives in the Taylor expansion.Source: §3.1 · pp. 9–10

3.2 Upper Bounding The Number of Constraints

  • The number of independent local constraints is bounded by representing the constraints at each received point as a linear map and bounding its rank.The rank bound for one received point can be multiplied by the number of received points to bound the total number of independent constraints.Source: §3.2 · p. 11, §3.2.2 · p. 16

3.2.1 A Bound on Λ(𝑧)’s Growth

  • A simplex-volume and centroid argument bounds the growth of Λ(z) and shows that the additional |c| restriction does not reduce B by too much.The proof samples a uniform point from a simplex, bounds its expected magnitude using its centroid, and applies Markov’s inequality.Source: §3.2.1 · p. 14

3.2.2 Bounding the Rank

  • The constraint map factors through an intermediate substitution and reduction, and divisibility by T^r E^h with r + dh ≥ m places a polynomial in the remaining map’s kernel.This kernel criterion supports the strategy of finding many linearly independent kernel vectors to upper-bound the map’s rank.Source: §3.2.2 · p. 16
  • Lemma 3.12 bounds the local rank of Γ by counting at most (r+1)(m+1)Λ(W+r) monomials in V for each fixed T-degree r and applying rank-nullity.The interpolation argument uses this rank bound to compare the number of homogeneous constraints with dim Q.Source: §3.2.2 · p. 18, §3.3 · p. 19

3.3 The Interpolation Lemma

  • Under k/n ≤ (1−θ)ε, A=⌈εn⌉, and condition (20), a nonzero Q exists whose derivative-evaluation composition vanishes for every degree-≤k−1 polynomial agreeing in at least A positions.At each agreement point the composition has multiplicity at least m; its degree is below mA, so it is identically zero.Source: §3.3 · p. 19

4 Algorithm and Analysis: Proof of Theorem 1.1

The section presents an interpolation-and-root-finding decoder and analyzes its guarantee in the low-rate regime. Its stated result gives efficient decoding for distinct evaluation points over a sufficiently large prime field.

4.1 The List-decoding Algorithm

  • The algorithm interpolates a multivariate polynomial using constraints at the received symbols, then invokes Kopparty’s algorithm to find candidate message polynomials.Source: §4.1 · p. 20, §4 · p. 20

4.2 Analysis

  • For rate at most (1−θ)ε, decoding to radius (1−ε)n takes q^O(ε^-12/θ) time with list size at most q^O(ε^-9/θ).The theorem applies when q is a sufficiently large prime and the evaluation points are distinct.Source: §4.2 · pp. 20–21
  • The analysis bounds the runtime by q^O(ε^-12/θ) and the number of polynomials found by q^O(ε^-3/θ).Source: §4.2 · p. 21

5 Extending to All Rates

For every fixed rate and slack, the theorem gives deterministic list decoding over prime fields for arbitrary distinct evaluation points. It achieves the stated agreement threshold with running time and list size bounded by q^{O_{R,δ}(1)}.

5 Extending to All Rates

  • The algorithm runs in q^{O_{R,δ}(1)} time and outputs a list of size at most q^{O_{R,δ}(1)} for polynomials agreeing in at least (R+δ)n positions.The theorem applies for every rate R∈(0,1), slack δ∈(0,1), and prime q≥Cn.Source: §5 · p. 22
  • The parameter choice ensures ηN≤A for sufficiently large n while keeping N=Θ_{R,δ}(n).The proof also requires η<R+δ and R/(1−θ)<R+δ.Source: §5 · p. 22
  • Padding the evaluation set to N points and the received word with zeros lets the algorithm for the extended code capture every qualifying original polynomial before pruning.The resulting pruned list is exactly the desired list for the original word.Source: §5 · pp. 22–23
  • Because η and θ depend only on R and δ, Theorem 4.1 gives the stated q^{O_{R,δ}(1)} bounds, and pruning adds only polynomial time in the list size.Source: §5 · p. 23

A A Proof of Theorem 3.9

The proof shows that a uniformly distributed point in a simplex has expectation equal to its centroid. It transfers the result from the standard simplex by an affine map, then uses symmetry and linearity of expectation.

A A Proof of Theorem 3.9

Related papers

Loading 2609.08005v1…