PaperlayerView exact revision on arXiv

Source-linked AI summary

Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding

Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami

arXiv:2610.36215v1cs.ITcs.CCmath.IT

TL;DR

The paper addresses the lack of deterministic Reed–Solomon evaluation-point constructions approaching list-decoding capacity. It constructs codes with a near-optimal subspace-design property and gives deterministic decoding, yielding capacity-level list decoding and line-decoding consequences.

  • Problem

    Explicit Reed–Solomon evaluation points approaching list-decoding capacity or the generalized Singleton bound were not known, despite probabilistic existence results.

    Source: §1 · pp. 3–4

  • Method

    The paper constructs Reed–Solomon codes that are near-optimal subspace-design codes over a subfield and uses deterministic algorithms and pruning methods to decode them.

    Source: §1 · p. 5, §1.1 · p. 6, §1.2 · pp. 11–12

  • Results

    The construction resolves the explicit evaluation-point question with a subspace-design property that yields list-decodability approaching the generalized Singleton bound and efficient guaranteed list decoding.

    Source: §1 · pp. 4–5

  • Takeaways & Limitations

    The subspace-design guarantee also supports line decoding over the extension field, with a stronger design assumption removing the affine-line reduction’s |F|/|K| threshold factor.

    Source: §1.2 · p. 12, §3.4 · p. 21

    The affine-line reduction incurs a |F|/|K| threshold factor; the improved line-decoding result avoids it under a stronger subspace-design assumption.

    Source: §3.4 · p. 21

Abstract

from arXiv · show

For any desired rate $R \in (0,1)$, and gap to list-decoding capacity $\varepsilon > 0$, we give an explicit $n^{O_{\varepsilon}(1)}$ time construction of Reed-Solomon codes over extension fields of size polynomial in the block length $n$ that can be list-decoded from a fraction $1-R-\varepsilon$ of errors with the optimal list-size of $O(\frac{1-R}{\varepsilon})$. We also give a simpler, strongly explicit construction of evaluation points for which the associated Reed-Solomon code can be list-decoded from $1-R-\varepsilon$ errors with list size $(1/\varepsilon)^{O(1/\varepsilon)}$. We provide a deterministic list-decoding algorithm for both constructions running in time $O_{\epsilon}(1)\mathsf{poly}(n)$. In fact, our Reed-Solomon codes are near-optimal subspace-design codes over a subfield. Via known results, this directly implies the combinatorial list-decoding guarantee, as well as near-optimal list-recovery bounds. We also present a new reduction showing that the subspace-design guarantee also implies line decoding over the extension field itself, which then yields proximity gaps and mutual correlated agreement up to proximity parameter approaching the optimal $1-R$ radius. Compared to the recent algorithm of Brakensiek, Chen, Putterman, Zhang, and Zheng (2026), which list decodes every Reed-Solomon code over prime fields up to capacity, our approach achieves constant (in fact, near-optimal) list size rather than a polynomially growing one, at the cost of carefully choosing the code's evaluation points. In a companion paper, we show that these respective restrictions are unavoidable.

1 Introduction

The introduction presents explicit Reed–Solomon evaluation-point constructions with strong list-decoding guarantees, deterministic decoding methods, and line-decoding and proximity-gap consequences from their subspace-design property. It also outlines the paper’s organization and discloses AI assistance.

1 Introduction

  • Although random Reed–Solomon evaluation points were known to achieve list-decoding capacity, deterministic evaluation-point constructions approaching capacity or the generalized Singleton bound remained open.This paper addresses whether Reed–Solomon codes themselves can attain capacity through suitable evaluation-point choices.Source: §1 · pp. 3–4

1.1 Our results

  • For every 1 ≤ d ≤ r, the constructed codes have τ(d)=min{1,R+ε/4} over every subfield K0 of K, giving near-optimal subspace-design guarantees.The subspace-design property implies list-decodability approaching the generalized Singleton bound, with list sizes up to r [CZ25].Source: §1.1 · p. 6
  • For every rate R, explicit extension-field Reed–Solomon codes achieve the generalized Singleton radius LL/(L+1)(1−R−ε) and deterministic decoding to distance 1−R−ε with list size O((1−R)/ε).The decoding algorithm runs in O_ε(1) poly(n, log |K|) time.Source: §1.1 · pp. 6–7
  • A simpler, strongly explicit construction gives Reed–Solomon codes list-decodable at radius 1−R−ε with list size (1/ε)^O(1/ε) and deterministic decoding.Its evaluation points can be computed individually in time poly(log |F|).Source: §1.1 · p. 7
  • Compared with, this work uses extension fields and carefully chosen evaluation points to obtain constant optimal list size, while handles arbitrary prime-field evaluation points with polynomial list size.The introduction states that these restrictions are necessary: without restricting fields or evaluation points, list sizes can grow super-polynomially just beyond the Johnson radius.Source: §1.1 · pp. 7–8
  • The subfield subspace-design guarantee is lifted to line decoding over the extension field F, yielding explicit proximity gaps and mutual correlated agreement approaching parameter 1−R.The construction achieves soundness poly(1/ε) at distance 1−R−ε with proximity loss γ.Source: §1.1 · pp. 8–9
  • The results include mutual correlated agreement.Source: §1.1 · p. 9

1.2 Technical overview

  • The authors’ effective-evaluation-point approach restricts possible determinant contributions, addressing the risk that evaluation points become roots of coordinate-specific determinants.The overview describes a clean proof after formalizing effective evaluation points and notes a construction of such points in Section 7.Source: §1.2 · pp. 9–10
  • A simpler evaluation-point construction gives list-decoding with list size Oε(1) and is strongly explicit, outputting each point in time poly(log |F|).It uses points of sufficiently high degree but does not fully control how many roots they contribute to det Ti.Source: §1.2 · p. 10
  • As a warmup, this procedure yields a deterministic folded Reed-Solomon list-decoder with improved ε-dependence over, while almost matching the best known list-size for this task [Tam24].The cited [GHKS24] decoders both run in near-linear time in n.Source: §1.2 · p. 11
  • The line-decoding method generalizes sampling-based pruning to leave a residual space of dimension below d, and guarantees that Ω(ε^2a) assigned codewords lie on a common codeword line.For any D-dimensional space, it samples S so that dim{a ∈ A | a_S = 0} < d and Pr[S ⊆ T] ≥ εD/d + ε for agreement sets T of size at least (R + ε)n; the line-decoding application chooses d = Ω(εD).Source: §1.2 · p. 12

1.3 Organization

  • The paper proceeds from definitions and combinatorial consequences to subspace-design proofs, list-decoding algorithms, evaluation-point constructions, and improved line-decoding and proximity-gap results.Appendix A presents the root-finding reduction using standard reductions and deterministic polynomial factorization.Source: §1.3 · p. 12

1.4 AI Disclosure

  • The authors disclose that ChatGPT assisted with construction ideas, algorithm development, technique refinement, line-decoding extensions, and exposition, while the authors assume responsibility for proof correctness and exposition quality.The disclosure credits human authors with developing definitions and generalizations including effectiveness and deterministic subspace-decoders.Source: §1.4 · pp. 12–13

2 Preliminaries

The preliminaries define Reed–Solomon and subspace-design codes, then state decoding consequences and algebraic tools used in the paper. These include deterministic constructions and bounds for independent conjugates under field automorphisms.

2 Preliminaries

  • A Reed–Solomon code evaluates degree-less-than-k polynomials at distinct field elements; it has dimension k and distance 1 − (k − 1)/n.The preliminaries also define code rate and relative Hamming distance.Source: §2 · p. 13

2.1 Subspace-design codes and decoding consequences

  • Subspace designs were introduced for restricting message spaces; later work gave explicit folded Reed–Solomon and constant-alphabet constructions.The section follows the terminology of, while a similar definition appeared in.Source: §2.1 · p. 13
  • Subspace-design codes support list-decoding and list-recovery guarantees, while curve decodability connects to proximity gaps and correlated agreement.The section defines subspace-design codes and gives the relationships among curve decoding, correlated agreement, proximity gaps, and mutual correlated agreement.Source: §2.1 · pp. 14–15

2.2 Polynomial modules and degree

  • Reduced K[X]-bases provide degree-controlled bases for polynomial modules, and the section states that they can be computed deterministically in polynomial time.For modules given by s generators of degree at most D, the stated operation count is poly(m, s, D + 1).Source: §2.2 · p. 16

2.3 Construction of Field Extensions and Deterministic Factorization

  • Finite-field polynomial factorization and construction of degree-d field extensions have deterministic algorithms running in polynomial time.The stated bounds are poly(d, log |F|) for factorization and poly(d, log |K|) for extension construction.Source: §2.3 · p. 17

2.4 Independent conjugates and coordinate movement

  • For independent polynomials over K(X), a downward-closed set of d independent conjugates can be computed deterministically in polynomial time and bounds how many conjugates move evaluation points.The movement bound in (2.2) is at most d log_2 d times the maximum number of points moved by a generator.Source: §2.4 · pp. 17–18

3 Main theorem and combinatorial consequences

The section presents explicit Reed–Solomon codes with near-optimal subspace-design guarantees and deterministic list decoding near capacity. It derives combinatorial guarantees for list recovery, curve and line decoding, proximity gaps, and correlated agreement.

3 Main theorem and combinatorial consequences

  • The construction gives Reed–Solomon codes that are near-optimal subspace-design codes over subfields, with deterministic list decoding from 1−R−ε errors and list size O((1−R)/ε).For every received word, lists within the stated radii can be found deterministically in time O_{r,ε}(1) poly(n, log |F|).Source: §3 · pp. 18–19

3.1 List recovery

  • The constructed codes are also shown to be capacity list-recoverable under the stated rate, error, and alphabet-list parameters.The theorem specifies 0<R<1, 0<ε<1−R, and integer ℓ≥2.Source: §3.1 · p. 19

3.2 Curve decoding

  • The section establishes capacity curve-decoding guarantees over the base field and, under an additional field-size condition, over the extension field.The extension-field result assumes |F|>(L+1)^{2ℓ} for sufficiently large n.Source: §3.2 · p. 20

3.3 Line decoding

  • The codes are shown to achieve capacity line decoding over the extension field for every integer t≥1.Source: §3.3 · p. 20

3.4 Proximity gap, correlated agreement, and mutual correlated agreement

  • The section derives correlated agreement and proximity-gap guarantees over F, and mutual correlated agreement over F.Source: §3.4 · p. 21
  • For line decoding, the affine-line reduction incurs a factor |F|/|K| in the curve-decoding threshold; a stronger subspace-design assumption removes that factor.Source: §3.4 · p. 21

4 Reed-Solomon Subspace Designs

The section gives sufficient evaluation-point conditions for Reed–Solomon codes to be subspace-design codes over a subfield. Its proof bounds coordinate kernels using Galois automorphisms and transfers the resulting rank guarantee to dimensions and smaller subfields.

4.1 Assumptions and the subspace-design theorem

  • The evaluation-point conditions combine Galois automorphisms fixing most points with a multiplicity bound for low-dimensional polynomial spaces.The definition requires a generating family of automorphisms and a condition on nonzero K-subspaces of dimension at most 2r.Source: §4.1 · p. 21
  • Effective evaluation points yield a Reed–Solomon code that is a τ-subspace-design over K, with τ(d)=1 for d>r.Source: §4.1 · p. 21

4.2 From effective evaluation points to subspace designs

  • The proof bounds coordinate-kernel behavior through K(X)-ranks, then transfers the guarantee to bounded K-dimensions; the same transfer extends the design property to subfields of K.The proof adapts a Wronskian-style argument using Moore/Galois determinants and automorphisms that fix most evaluation points.Source: §4.2 · pp. 22–23, §4.1 · p. 22

4.3 Proof of the transfer theorem

  • The transfer theorem converts a guarantee on small E0-subspaces into a weighted dimension guarantee, enabling the passage from extension-field ranks to subspace-design bounds.Source: §4.2 · p. 23, §4.3 · p. 24

5 Efficient List Decoding

The section gives a deterministic list-decoding algorithm for Reed–Solomon codes near capacity. Its blueprint first finds a low-dimensional K(X)-space containing nearby message polynomials, then prunes that space to obtain the output list.

5 Efficient List Decoding

  • The decoder finds a low-dimensional K(X)-space containing every close-by message polynomial, then prunes it using low-degree constraints.Source: §5 · p. 25

The output list has size at most

  • The list-decoding theorem applies when evaluation points are pairwise nonconjugate over K, have sufficiently high comparable degrees, and satisfy an automorphism condition.Source: §5 · p. 25
  • A strongly explicit construction computes each evaluation point in time poly(log |F|) and supports deterministic list decoding in time O_ε(1) poly(n, log |F|).Source: The output list has size at most · p. 25

5.1 The two-step list-decoding theorems

  • The algorithm outputs all degree-less-than-k polynomials agreeing with the received word on at least k+εn positions, with deterministic running time O_{d,ε}(1) poly(n, log |F|) for the pruning step.Source: §5.1 · p. 26, The list has size at most · p. 26

5.2 Finding a low-dimensional K(X)-space (Theorem 5.2)

  • Dimension reduction repeatedly replaces a K(X)-space by a strict subspace that preserves all qualifying polynomials, until its dimension is at most 2/ε.The reduction runs in time poly(n,g,log |F|) per construction and preserves a basis of degree-less-than-k polynomials.Source: §5.2 · pp. 27–28

6 Pruning low-dimensional spaces of Reed-Solomon codes

This section develops a deterministic pruning procedure that extracts qualifying Reed–Solomon codewords from a low-dimensional space. It also applies the pruning approach to folded Reed–Solomon decoding.

6 Pruning low-dimensional spaces of Reed-Solomon codes

  • Given a low-dimensional K(X)-linear space, the pruning theorem outputs all degree-less-than-k polynomials in that space meeting the agreement condition, in time O_{d,ε}(1) poly(n, log |F|).Source: §6 · p. 28, The list has size at most · p. 28

The list has size at most

  • The pruning procedure branches on polynomial constraints when its current constraint set fails to determine the candidate space, with branching rules that reduce the remaining search.The text identifies three failure cases and describes branching on ℓ or r when ℓr lies in the constraint set.Source: The list has size at most · p. 29
  • The paper applies its subspace-decoding result to improve the deterministic list-decoding running time for folded Reed–Solomon codes.Source: The list has size at most · p. 29
  • For an s-folded Reed–Solomon code with m=⌈2/ε⌉ and s=m², a deterministic algorithm outputs messages agreeing with the received word on at least (R+ε)n coordinates.Source: The list has size at most · p. 30

6.1 Pruning for F-subspaces of Reed-Solomon codes (Theorem 6.1)

The decoding procedure maintains a ready space of relations and repeatedly adds a new relation or branches to reduce the remaining search. An inductive analysis bounds the output list size and establishes the theorem.

6.1 Pruning for F-subspaces of Reed-Solomon codes (Theorem 6.1)

  • The procedure maintains an F-linear relation space on a basis of the candidate subspace and closes it under an operation that preserves its common zero set.Coordinates whose evaluation relations lie in the space are treated as determined; the remaining coordinates guide the search.Source: §6.1 · p. 30

6.1.1 Interpolate a new relation or branch

  • Interpolation either supplies a new relation vanishing on candidate messages or branches on an undetermined coordinate, with the branches covering every current common zero.The new relation strictly reduces the remaining monomials; the two branches add independent constraints.Source: §6.1.1 · pp. 31, 33, §6.1.2 · p. 33

6.1.2 Bounding the Output List-Size

  • An induction over the remaining monomials bounds the output list, and the theorem’s proof uses deterministic fast interpolation to find new relations.The interpolation step has a stated cost of eO(n|Pt|^3) field operations; the proof also accounts for branch steps and terminal checks.Source: §6.1.2 · pp. 33–35

6.2 Pruning K(X)-subspaces (Theorem 5.3)

This section extends relation pruning to K(X)-subspaces, using degree control, specialization at evaluation points, interpolation, and branching to reduce the candidates to relations or a uniquely checkable message. It bounds the resulting search tree and running time to complete the proof of Theorem 5.3.

6.2 Pruning K(X)-subspaces (Theorem 5.3)

  • Preparation preserves the polynomial zeros under consideration and bounds the exceptional coordinates by εn/16; at regular coordinates, evaluated pivot monomials and complements are unchanged.A prepared space has stored-matrix degree at most B(d,t)k, which supplies the bound on exceptional coordinates.Source: §6.2 · pp. 36–37

6.2.1 Finding a new relation

  • Interpolation yields a new relation vanishing on relevant polynomial tuples, spans all of S_t with R, or identifies at least k determined coordinates.In the first case, the added relation vanishes identically on tuples c(X) with Enc(c) in L; k determined coordinates leave at most one message polynomial.Source: §6.2 · p. 37, §6.2.1 · pp. 38–39

6.2.2 From interpolation failure to branching

  • When interpolation fails, the algorithm computes either a relation outside R vanishing on Z(R) or a nonzero branching form, deterministically in O_{d,ε}(1) poly(n, log |F|) time.It branches into R ∪ {ℓu} and R ∪ {p ∈ W_{t−1} : pℓu ∈ R}.Source: §6.2.2 · pp. 39, 41

6.2.3 Bounding the list and the running time

  • The list-size and running-time analysis applies Claim 6.7’s induction at each branching step.The supplied passage states that the induction applies because every branching step satisfies its condition.Source: §6.2.3 · p. 42
  • The dimension of R strictly increases along each branch, and the binary tree has depth at most |Mt| and O_{d,ε}(1) nodes.The choice in (6.4) satisfies C(d, ε) = exp(O(d^3 log(1/ε))).Source: §6.2.3 · p. 42
  • The total running time is O_{d,ε}(1) poly(n, log |F|), with finding a common zero as in Theorem 6.18 the main cost at each node.The remaining operations take O_{d,ε}(1) poly(n, log |F|) time.Source: §6.2.3 · p. 42
  • This establishes Theorem 5.3.Source: §6.2.3 · p. 42

7 Effective Evaluation Points and Explicit Instantiation

The section gives a strongly explicit construction and a separate effective construction of Reed–Solomon evaluation points. The latter satisfies subspace-design conditions while keeping the extension degree bounded in terms of the construction parameters.

Strongly explicit evaluation points

  • The simpler strongly explicit construction supports list decoding at gap ε to capacity with list size (1/ε)^O(1/ε).Its evaluation-point construction is described as sufficient for the list-decoding application, though it does not achieve the paper’s effectiveness definition.Source: §7 · p. 42
  • The strongly explicit algorithm outputs irreducible polynomials deterministically in time poly(g, d, log |K|), while the effective points can be found in time |K|^O_d,g(1).The effective construction uses points selected from translates of roots of the constructed polynomials.Source: §7 · pp. 42–43

Effective evaluation points

  • The effective construction provides an extension F/K of degree at most (d + g)^O(g) with points satisfying the stated subspace-design conditions.The theorem assumes fixed r ≥ 2, g ≥ 2r, n ≥ g, and |K| > nr.Source: §7 · pp. 42–43
  • The effective points have degrees over K within a factor of two of one another and at least d, and each indexed point can be output in poly(log |F|) time.These are among the construction’s stated properties.Source: §7 · pp. 42–43

8 Improved line decoding and proximity gaps

The section reduces line decoding over an extension field to a subspace-design guarantee over a subfield. Applied to the paper’s codes, this yields capacity-near line-decoding and related proximity-gap and agreement consequences.

8 Improved line decoding and proximity gaps

  • Theorem 8.1 converts a subspace-design bound over K into line decoding over the extension field F for an F-additive code.The theorem is stated for a broader finite-dimensional F-vector-space alphabet, though the paper applies it with alphabet F.Source: §8 · p. 45

8.1 Improved combinatorial consequences

  • The constructed codes are both (1 − R − ε/2, L)-list-decodable and (δ, a0, b0)-F-line-decodable, with the theorem’s parameters chosen from the gap to capacity.The corollary applies for sufficiently large n and finite fields K with |K| ≥ n.Source: §8.1 · pp. 45–46
  • The corollary also gives improved proximity-gap and correlated-agreement conclusions over F.The theorem application takes all line parameters and probabilities over F.Source: §8.1 · p. 46
  • The resulting parameters satisfy L, b0 = O(ε^-1), a0 = O(ε^-3), and r = 2^O(ε^-3); the design order and required extension degree depend only on ε.The line-decoding threshold estimates have denominator |F| and no factor |F|/|K| in a0.Source: §8.1 · p. 46

8.2 Proof of the extension-field line-decoding theorem

  • The proof builds a K-subspace from codewords assigned to received-line parameters, applies the design bound and pruning, then shows the consistent codewords lie on a codeword line.The proof uses slow growth of monomial-space dimensions to bound the subspace dimension before pruning.Source: §8.2 · p. 48

A Computing a common zero

The lemma gives a deterministic procedure for deciding whether a polynomial system has a common zero over K(X) and, if so, computing one in a represented finite extension. It constructs the zero coordinate by coordinate, with controlled extension and coefficient degrees.

A Computing a common zero

  • Factoring over the successive finite extensions is reduced to polynomially many bivariate factorizations, with deterministic time O_{m,d}(1) poly(h, log |K|) and controlled output coefficient degrees.The factorization procedure handles polynomials over E with rational-function data of degree at most h.Source: A Computing a common zero · pp. 56–57
  • At each coordinate, the algorithm factors a polynomial of degree at most B and tests its irreducible factors, or selects a value from 1, X, ..., X^B without extending the coefficient field.In the factorization case, a passing factor defines the next extension; in the other case, a nonzero minor certifies the selected value preserves a common zero.Source: A Computing a common zero · p. 58
  • The procedure computes a common zero in a finite extension represented by defining polynomials and an L-basis, with extension degree at most B^a.Here L = K(X); the per-coordinate degree bound is B.Source: A Computing a common zero · pp. 56, 58
  • The deterministic running time is O_{s,D,a}(1) poly(H, log |K|), with coefficient degrees remaining O_{s,D,a}(1) poly(H).The analysis bounds the degree growth through linear-system computations, factorization, extension-table construction, and substitutions.Source: A Computing a common zero · p. 58

Related papers

Loading 2610.36215v1…