Source-linked AI summary
Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi
TL;DR
Finding the agreement threshold that keeps Reed-Solomon list sizes bounded, and efficiently finding the resulting lists, has long been an open problem. Theorem 1.1 gives algorithmic list decoding up to capacity over large-characteristic fields [BCPZZ26], and Jeronimo extended the techniques to the proximity-gaps question [Jer26].
Problem
The open problem is where Reed-Solomon list sizes remain bounded and an efficient algorithm can find the resulting lists; proximity gaps are a related open question.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
Jeronimo extended the techniques to solve the proximity-gaps question for Reed-Solomon codes [Jer26].
Source: §1 · p. 2A further apparent algebraic relationship with the received word is insufficient by itself to list-decode beyond the Johnson radius.
Source: Algorithmic list-decoding ([BCPZZ26]) · p. 4
Abstract
from arXiv · showhide
Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to solve the proximity-gaps question for RS codes. In this article, we give a unified and transparent exposition of these results.
1 Introduction
The section gives a unified exposition of capacity-level algorithmic list-decoding for Reed–Solomon codes over suitable large-characteristic fields and Jeronimo’s proximity-gap result for correlated agreements. It outlines the proof ingredients, including the reduction to an agreement threshold of k(1 + ε) and pruning to bound list size and identify values without coordinated agreement.
1 Introduction
- [BCPZZ26] gives an algorithm that lists every degree-<k polynomial agreeing in at least k(1 + ε) positions, in time q^C(ε,ρ), when q ≥ n, p > k, and k/n ≥ ρ.The theorem assumes sufficiently large k and n; C depends on ε and ρ.Source: §1 · p. 2
- Jeronimo [Jer26] shows that if at least L = n^C(ε,ρ) values of ζ yield a degree-<k polynomial with k(1 + ε) agreements, then u and v have at least k(1 + ε) correlated agreements with a pair of degree-<k polynomials.Consequently, u + ζv has at least k(1 + ε) agreements with the Reed-Solomon code for every ζ; the stated result assumes q ≥ n and p > k.Source: §1 · p. 2
- The exposition gives proofs of both results, highlights key ideas, and makes slight parameter improvements; its proof directly covers all rates and evaluation-point sets without the Alrabiah-Goyal-Guruswami reduction.It is largely self-contained apart from a few standard facts from algebraic geometry and coding theory.Source: §1 · pp. 2–3
Algorithmic list-decoding ([BCPZZ26])
- [BCPZZ26] adapts polynomial interpolation by treating unavailable high-order derivatives as formal variables, but that information alone cannot extend list-decoding beyond the Johnson radius.The proof uses a reverse Taylor relation to connect the derivatives and evaluations algebraically.Source: Algorithmic list-decoding ([BCPZZ26]) · p. 4
- In [BCPZZ26], choosing B=Λ(W) makes |B+Λ(m)|/|B| exactly estimable and yields a bound on A of the form (1 + ε)k.The proof then uses Kopparty’s differential equation solver to recover messages; setting d to a constant makes the list size polynomially bounded and the solver polynomial-time.Source: Algorithmic list-decoding ([BCPZZ26]) · p. 5
Proximity gaps for Reed-Solomon codes [Jer26]
- [Jer26] reduces the proximity-gap agreement threshold to k(1 + ε) and uses pruning to bound the list of polynomials by a polynomial in n.The polynomial’s exponent depends only on rate ρ and ε, independent of field size; the pruning works with varieties rather than affine subspaces and uses basic algebraic geometry.Source: Proximity gaps for Reed-Solomon codes… · p. 6
- Given the pruning method, [Jer26] bounds the number of values of ζ for which there is no coordinated agreement.Source: Proximity gaps for Reed-Solomon codes… · p. 6
2 Notation and preliminaries
This section fixes tuple notation and recalls Hasse derivatives and polynomial multiplicity, alongside a monomial-counting fact used in the algorithm.
2 Notation and preliminaries
- Boldface letters denote tuples such as y = (y1, . . . , yk).Source: §2 · p. 6
- Hasse derivatives are the coefficients in the Taylor expansion of f(X + T), with f^(0)(X) = f.The expansion continues with f^(i)(X) as the coefficient of T^i.Source: §2 · pp. 6–7
- Because the results apply only to large-characteristic fields, the exposition notes that standard derivatives could also be used but adopts Hasse derivatives.Source: §2 · p. 7
- A polynomial has a root α of multiplicity m when (X − α)^m divides it.Source: §2 · p. 7
- Fact 2.1 counts monomials X^aY^b satisfying a + kb < D.The fact is identified as a standard combinatorial input to the algorithm.Source: §2 · p. 7
3 Sudan’s template for algebraic decoding algorithms
This section presents an algebraic Reed–Solomon decoding template that builds an explainer polynomial and extracts candidates with many agreements, highlighting hidden derivatives as an adaptation of multiplicity-code decoding. It describes how derivative substitutions affect the constraint count and how controlling the enlarged exponent set supports pushing the agreement threshold to A = k(1 + ε).
3 Sudan’s template for algebraic decoding algorithms
- The decoding template builds an explainer polynomial Q from the received word, then extracts polynomials f whose agreement with it is at least A.The paper identifies this template with Gemmell and Sudan for unique decoding and Sudan for list decoding.Source: §3 · pp. 7–8
- [BCPZZ26] adds hidden derivatives to the standard template, adapting Kopparty’s univariate multiplicity-code decoder to Reed-Solomon codes.The paper presents this ingredient as the route to decoding beyond the Johnson radius.Source: §3 · p. 8, §3.3 · p. 11
3.1 Guruswami-Sudan’s list-decoding algorithm
- In Guruswami–Sudan decoding, if a degree-less-than-k polynomial f agrees at least A times, then Q(X, f(X)) is identically zero, making Y − f(X) a factor of Q.Factoring Q therefore recovers the candidate polynomials.Source: §3.1 · pp. 8–9
3.2 Using additional derivatives
- Higher-derivative decoding uses a multivariate Q whose substitution of f and its Hasse derivatives yields a differential equation; Kopparty’s solver enumerates solutions when char(Fq) = p > k.The naive interpolation setup offers no gain because both the interpolation-space estimate and constraint count scale with |B|.Source: §3.2 · p. 10
3.3 The key insight: hidden derivatives
- [BCPZZ26] uses a reverse Taylor relation to connect evaluations with higher derivatives; with one hidden derivative, the method already goes beyond the Johnson radius.For d = 1, f(α_i + T) = y_i + T f^(1)(α_i + T) + E, where E = 0 mod T^2.Source: §3.3 · p. 11
3.3.1 Breaching the Johnson radius
- For d = 1, Gabizon studied decoding beyond the Johnson radius and provided a linear list size; the interpolation setup bounds a + kr + kb < mA and b < Lm.It imposes constraints for monomials with a + 2r < m.Source: §3.3.1 · p. 11
- With sufficiently many hidden derivatives, the agreement threshold reaches A = k(1 + ε) for arbitrarily small ε; at small rate, a large L suffices even with one derivative.Source: §3.3.1 · p. 12
3.4 High-level picture for the general case
- The general construction substitutes the candidate’s derivatives into Q at α_i + T; when f(y_i) = α_i, the resulting expression is divisible by T^m, with E expected to vanish modulo T^(d+1).Source: §3.4 · p. 12
- Restricting zero-coefficient constraints to monomials with a + (d + 1)r < m saves a factor of d + 1, but substitution enlarges possible Y-exponent vectors from B to B + Lambda(m).Source: §3.4 · pp. 12–13
- For the simplex choice B_d, B + Lambda(m) can be large enough to offset the earlier counting gain.Source: §3.4 · p. 13
- The section therefore proposes B = Lambda(W), for suitable W, to keep B + Lambda(m) from growing much larger than B.Source: §3.4 · p. 13
- The proof’s remaining care lies in choosing W and analyzing the size of Lambda(W) and the average total exponent over its elements.Source: §3.4 · p. 14
4 The simplex Λ(W)
Section 4 relates the discrete simplex Λ(W) to its continuous counterpart and gives facts about its size and the expected coordinates of a uniformly chosen point.
4.1 Counting points in Λ(W)
- The unit-cube argument relates the discrete set Λ(W) to the continuous simplex λ(W), bounding their volumes through containment.Each point b in Λ(W) is associated with the cube b + [0,1)^d; the proof also places the union of these cubes inside λ(W + d^2).Source: §4.1 · p. 14
- For W = Ω(d^4), Corollary 4.2 approximates |Λ(W)| using the volume of λ(W).The displayed relative-error term is incomplete in the supplied passage.Source: §4.1 · p. 14
4.2 Expected value of a coordinate in Λ(W)
- For W = Ω(d^4), Fact 4.3 gives the expected value of coordinate b_i under the uniform distribution on Λ(W).The passage states E[b_i] = W i(d + 1) + O_d(1).Source: §4.2 · p. 15
5 Algorithmic list-decoding: completing the proof
The proof constructs an interpolation polynomial Q by imposing local constraints at received symbols, then uses a differential-equation solver to recover and filter candidate message polynomials.
5 Algorithmic list-decoding: completing the proof
- The local constraints set coefficients to zero after substituting the received symbol and the polynomial’s derivative-based expansion.For indices with a + (d + 1)r < m, the constraint is q_i,a,r,c = 0.Source: §5 · p. 16
- A nonzero Q satisfying the constraints exists when its number of indeterminates exceeds the number of imposed constraints.The constraint count is at most n · m^2(1 + o(1)).Source: §5 · p. 16
- The algorithm finds a nonzero Q by solving a linear system, then applies a differential-equation solver to obtain candidate polynomials.It returns candidates of degree less than k that agree with the received word in at least k(1 + ε) locations.Source: §5 · pp. 16–17
6 Proximity gaps
This section sketches Jeronimo’s extension of proximity-gap results for Reed–Solomon codes to agreement barely above capacity, using interpolant-based decoding and algebraic pruning. It covers how rational-map images describe high-agreement pairs outside an exceptional set and how bounding that set yields correlated agreements.
6 Proximity gaps
- The proximity-gap problem asks whether many agreements of u + ζv with degree-<k codewords force u and v to share correlated agreement with degree-<k polynomials.Earlier results of Ben-Sasson, Carmon, Ishai, Kopparty, and Saraf covered the unique-decoding or Johnson-radius regimes; the open regime was A = k(1 + ε) for arbitrarily small ε.Source: §6 · p. 17
6.1 Overall sketch
- A small collection of low-dimensional, low-degree varieties covers high-agreement pairs, and pruning bounds exceptional ζ values by |B| + M(nD)^O(d).The varieties have dimension at most d + 1 and degree at most n·poly(d); pruning successively intersects them with agreement hyperplanes.Source: §6.1 · pp. 18–19
- For ρ, ε > 0 and sufficiently large k,n with k/n ≥ ρ, n ≥ k(1 + ε), and p ≥ k, at least L qualifying ζ yield degree-<k polynomials g,h with correlated agreement ≥ k(1 + ε).Source: §6.1 · p. 20
6.2 Setting the interpolant system of equations over F(Z)
- An interpolant over F[Z] can be constructed with degree in Z at most 2^poly(d)·n^2.The construction treats the received word as u + Zv and applies Cramer’s rule to the interpolant constraints.Source: §6.2 · pp. 20–21
6.3 Kopparty’s differential equation solver
- When char(F) > max(k, deg_Yi(P)), Kopparty’s differential equation solver gives rational functions that reconstruct f from its first d Taylor terms given suitable initial conditions.The stated reconstruction applies when the top variable of P is preserved under Z = ζ and P(ζ, X, f, f(1), …, f(d)) = 0.Source: §6.3 · p. 21
- For ζ outside B, any degree-less-than-k polynomial f satisfying Q_Z(X, f, f^(1), …, f^(d)) = 0 maps to (ζ, f) in some Ψ_{P,γ} image.The condition uses a set T of size at least mA.Source: §6.3 · p. 22
- Every pair (ζ, f) with at least A agreements lies in B × F^k or one of the varieties V_{P,γ}, each of dimension at most d + 2.Each variety has degree at most 2^poly(d) · n^O(d).Source: §6.3 · p. 23
6.4 Bounding the final bad set of ζ’s
- The exceptional set B has size at most n^2 · 2^poly(d).Source: §6.4 · p. 23
- When p ≫ n^O(d^2) · 2^poly(d), even a small fraction of ζ’s witnessing A agreements to RS[n, k] yields a correlated set of A agreements.The covering varieties number n · 2^poly(d), have dimension O(d), and each has degree at most 2^poly(d) · n^O(d); this completes the proof of Theorem 1.2.Source: §6.4 · p. 23
A A brief primer on algebraic geometry
The primer introduces algebraic varieties and the notions of dimension and degree, then presents the Zariski-topology and Bézout tools used in the write-up.
A A brief primer on algebraic geometry
- An algebraic variety is a common zero set of finitely many polynomials, and irreducibility rules out expressing it as a nontrivial union of two varieties.Dimension is defined through generic affine-subspace intersections, and degree counts the resulting finite intersection points.Source: A A brief primer on algebraic geometry · p. 25
- The Zariski topology takes varieties as closed sets; polynomial maps are continuous, and images and closures of irreducible spaces remain irreducible.Rational maps are continuous where their denominators do not vanish.Source: A A brief primer on algebraic geometry · p. 25
- Bézout’s theorem bounds the sum of the degrees of a variety’s irreducible components by the product of the defining polynomials’ degrees.The primer uses this theorem to bound the size of a generic intersection.Source: A A brief primer on algebraic geometry · p. 25
- For a rational map from d coordinates, the closure of its image is irreducible, has dimension at most d, and has degree bounded using Bézout’s theorem.The proof sketch intersects the image closure with a generic affine subspace and bounds the resulting finite set via polynomial constraints.Source: A A brief primer on algebraic geometry · pp. 25–26
B Deferred proofs
The deferred proof compares lattice-point expectations with a continuous relaxation, using symmetry of an augmented simplex.
B Deferred proofs
- A continuous relaxation is used to relate a lattice-point count to a volume bound.The proof then compares expectations over the continuous region and the discrete set.Source: B Deferred proofs · pp. 26–27
- Adding a slack coordinate makes the simplex symmetric, so every coordinate has expectation W/(d+1).A coordinate-wise scaling transfers this symmetry-based expectation to the original coordinates.Source: B Deferred proofs · p. 26
- Half-open unit cubes around lattice points relate the discrete expectation to the continuous one.The proof uses this comparison to obtain an expectation for the sum of the lattice coordinates.Source: B Deferred proofs · pp. 26–27
C Degree bounds for Kopparty’s reconstruction algorithm
This section bounds the degrees in Kopparty’s reconstruction by expressing higher Taylor coefficients through rational functions and controlling their growth with a derivation operator.
C Degree bounds for Kopparty’s reconstruction algorithm
- The reconstruction yields polynomial upper bounds on the degrees of the rational functions’ numerators and denominators.The stated bounds include deg NP,i ≤ 2(i − j)·deg P and e ≤ 2(i − j).Source: C Degree bounds for Kopparty’s… · p. 27
- Unlike the repeated-composition reconstruction in [Kop15], the modified procedure avoids the apparent superpolynomial degree growth.The section notes that such growth is not in fact incurred and establishes polynomial degree bounds.Source: C Degree bounds for Kopparty’s… · pp. 27–28
- The argument assumes sufficiently large characteristic and a nonvanishing partial derivative condition at the chosen point.It also assumes the specialized polynomial retains the relevant top variable and that f satisfies the polynomial relation.Source: C Degree bounds for Kopparty’s… · pp. 27–28
- Higher Taylor coefficients are recovered iteratively by differentiating a rational expression and evaluating it at γ.The coefficients a0 through ad and the parameter Z provide the initial data for this recovery.Source: C Degree bounds for Kopparty’s… · p. 28
- The derivation operator D captures differentiation of h(Z, X, Δ(f)) through the chain rule.Its terms encode the derivatives with respect to X and the Y variables, including the expression ΓP for the next derivative.Source: C Degree bounds for Kopparty’s… · p. 29
- Repeated applications of D to Yd produce the rational expressions for later coefficients, with degree growth bounded using properties of D.The bounds control the numerator degree and denominator through powers of ∂Yd(P).Source: C Degree bounds for Kopparty’s… · p. 30