Source-linked AI summary
Deterministic Constructions of Reed-Solomon Codes Beyond the Johnson Bound
Abhranil Chatterjee, Sumanta Ghosh, Zeyu Guo, Rohit Gurjar, Roshan Raj, Zihan Zhang
TL;DR
The paper addresses the search for deterministic Reed–Solomon evaluation points with strong list-decoding guarantees. It uses structured isolating weights and a Vandermonde substitution to preserve determinant nonzeroness. The resulting constructions provide codes beyond the Johnson radius and MDS(3) codes with quasipolynomial field-size and construction-time bounds.
Problem
The paper seeks deterministic evaluation points for Reed–Solomon codes with strong list-decoding guarantees, including in small characteristic.
Source: §1 · p. 3Method
The construction uses matroid-intersection isolating weights to build a Vandermonde substitution that preserves nonzeroness of determinant polynomials.
Source: §1.1 · p. 5, §1.2 · p. 6Results
The construction yields (1−ε,O(1/ε)) list-decodable Reed–Solomon codes in quasi-polynomial time over fields of size at most (nk)^quasi-poly(nk), and deterministic MDS(3) codes for all 1≤k<n.
Source: §1.1 · p. 4Takeaways & Limitations
The same determinant-preserving construction supports both beyond-Johnson list decoding and the first nontrivial higher-order MDS case.
Source: §1.1 · pp. 4–5The stated assumption requires q>L and L≤k<n.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We give a deterministic quasipolynomial-time construction of Reed-Solomon codes that are list-decodable beyond the Johnson radius. Specifically, for every $\epsilon\in(0,1]$ and all sufficiently large $n$, we construct an $[n,k]$ Reed-Solomon code of rate $R=\Omega(\epsilon/(1+\log(1/\epsilon)))$ over a field of size $(nk)^{quasi-poly(nk)}$ that is $(1-\epsilon,O(1/\epsilon))$ list-decodable. The construction runs in quasi-poly(nk) time. We also give a deterministic construction of $[n,k]$-MDS$(3)$ Reed-Solomon codes for all integers $1\leq k<n$, with the same asymptotic bounds on field size and construction time. In the constant-rate regime, our field-size bound substantially improves the bound of $O(n^{k^{2k}})$ achieved by Roth's construction (Roth, IEEE TIT 2022). Our constructions exploit a connection to polynomial identity testing for read-once determinants, together with the quasipolynomial isolating-weight construction of Gurjar and Thierauf for linear matroid intersection (Gurjar and Thierauf, STOC 2017 and Computational Complexity 2020).
1 Introduction
The introduction motivates deterministic Reed–Solomon constructions with strong list-decoding guarantees, then presents results beyond the Johnson radius and for MDS(3). Its proof idea connects coding-theoretic determinant conditions to polynomial identity testing and isolating weights for matroid intersection.
1 Introduction
- The paper seeks deterministic evaluation points with guarantees comparable to random Reed–Solomon codes, including in small characteristic.The authors also frame the problem as a setting for developing derandomization techniques for structured algebraic problems.Source: §1 · p. 3
1.1 Main Results
- The construction gives deterministic [n,k] Reed–Solomon codes that are (1−ε,O(1/ε)) list-decodable in quasi-polynomial time over fields of size at most (nk)^quasi-poly(nk).For sufficiently small ε and sufficiently large n, the stated radius 1−ε exceeds the Johnson radius.Source: §1.1 · p. 4
- For every 1≤k<n, a deterministic quasi-polynomial-time construction produces an [n,k] Reed–Solomon code with the MDS(3) property over a field of size at most (nk)^quasi-poly(nk).MDS(3) is the first nontrivial higher-order case; MDS(1) and MDS(2) are equivalent to ordinary MDS.Source: §1.1 · p. 4
1.2 Proof Idea
- Both coding properties reduce to preserving nonzeroness of determinant polynomials, and the paper uses isolating weights for matroid intersection to construct a compatible Vandermonde substitution.The partition-matroid structure enables isolating weights of the form needed to realize the substitution through Reed–Solomon evaluation points.Source: §1.2 · pp. 5–6, §1.1 · p. 5
- The method builds a quasipolynomial-size family of specially structured isolating weights, combines them by polynomial interpolation, and evaluates the resulting map over an extension field.The resulting framework is applied to determinant characterizations of both list decoding and MDS(3).Source: §1.2 · p. 6
2 Preliminaries and Notation
This section introduces matroids and matroid intersection, then develops isolating weights for finding a unique maximum-weight common base. The construction uses cycles associated with faces of the matroid-intersection polytope.
2 Preliminaries and Notation
- A matroid’s independent sets are closed under subsets and satisfy augmentation, yielding bases of equal size that obey base exchange.The rank is the size of a base.Source: §2 · p. 6
- Linear matroids represent bases through nonzero determinants, while partition matroids prescribe how many elements each part contributes to a base.The paper’s M_k,J partition matroid has one rank-one part for each j in J.Source: §2 · p. 7
- Matroid intersection seeks a common base, and its polytope is described by rank inequalities for both matroids together with a fixed total rank.Faces are characterized using partitions whose unions encode tight rank constraints and elements fixed to zero.Source: §2 · p. 7, §2.1 · p. 8
2.1 Isolating Weight Assignment for Matroid Intersection
- An isolating weight vector makes one common base uniquely maximum-weight; the section’s lemma builds such weights by separating cycle circulations.Cycles alternate between parts of the two partitions associated with a face; the lemma combines weight vectors with nonzero circulation on the selected cycles.Source: §2.1 · pp. 7–8
3 Proof of Theorem 1.5
The proof recasts determinant nonzeroness as a common-base problem and constructs isolating weights compatible with Reed–Solomon substitutions. It uses these weights to find evaluation points that preserve nonzero determinants across subsets.
3 Proof of Theorem 1.5
- The determinant’s monomial support is the family of common bases of the partition matroid and the matroid represented by U2.An isolating weight gives a unique maximum-weight support set, preventing its monomial from canceling after substitution.Source: §3 · p. 9
- The partition-matroid structure makes each simple cycle pairable within distinct parts, enabling weights with nonzero circulation on prescribed cycle collections.The construction uses a family U of size approximately Õ(ns) with entries bounded by approximately Õ(nks).Source: §3 · pp. 9–11
- A quasipolynomial-size family of bounded-coordinate weights isolates common bases for any matroid sharing a common base with M_k,[n].The weights have coordinates w_i,j = (i − 1)e_wj.Source: §3 · p. 11
- Interpolation builds a bivariate substitution that preserves a nonzero determinant; Kronecker substitution then converts it to a nonzero univariate polynomial.A field extension element of degree at least D yields evaluation points that simultaneously preserve nonzeroness for all matrix pairs.Source: §3 · pp. 12–13
- C, D ≤ (nk)^O(log(nk)); the constructed evaluation points are pairwise distinct and preserve determinant nonzeroness for every subset J and eligible matrix pair.The construction is deterministic and uses quasipolynomially many arithmetic operations for interpolation and evaluation.Source: §3 · pp. 13–14
4 Proof of Theorem 1.1
The proof reduces beyond-Johnson list decoding to rank-preservation conditions on intersection matrices, then constructs evaluation points that satisfy those conditions. The resulting Reed–Solomon code has rate k/n and is (1−ε,t−1) list-decodable, with quasipolynomial construction time and field size.
Intersection-matrix condition
- The proof uses the sufficient condition from to express beyond-Johnson list decodability in terms of intersection matrices.The theorem’s relevant matrix determinants are shown to have the form needed for direct construction of evaluation points.Source: §4 · pp. 14–15
Determinant reduction
- Theorem 4.3’s determinant reduction relies on the cycle-space matrix B_t, whose rows form a basis of the complete graph’s cycle space.The proof constructs the matrix factorization using this cycle-space structure.Source: §4 · pp. 14–15
Theorem 4.2
- Theorem 4.2 gives a sufficient rank-preservation condition under which the Reed–Solomon code has rate k/n and is (1−ε,t−1) list-decodable.Here t=⌈2/ε⌉; the condition compares full rank over a rational-function field with full rank after substituting the evaluation points.Source: §4 · p. 15
Construction
- The evaluation points, and hence the code, are constructed in quasi-poly(nk) time over a field of size at most (nk)^quasi-poly(nk).The proof obtains the points using Theorem 1.5.Source: §4 · p. 18
5 Proof of Theorem 1.3
The proof constructs evaluation points that meet the matrix conditions characterizing MDS(3) Reed–Solomon codes. It obtains an [n,k]-MDS(3) code with quasipolynomial construction time and field size.
Determinant reduction
- The proof reduces the required determinants to the form handled by Theorem 1.5, enabling direct construction of evaluation points.For dimensions k′<k, padding adds parallel columns to one matrix and zero columns to the other, leaving the determinant unchanged.Source: §5 · p. 19
Matrix condition
- The construction uses pairwise disjoint sets A1, A2, A3 whose sizes sum to 2k to verify the 3-MDS matrix condition.The argument for k′<k extends the k′=k case using the padding construction.Source: §5 · p. 21
MDS(3) construction
- The constructed Reed–Solomon code is [n,k]-MDS(3).The proof verifies the required matrix condition using the equivalent characterization for these codes.Source: §5 · pp. 18, 19, 22
Construction bounds
- The evaluation points are constructible in quasi-poly(nk) time over a field of size at most (nk)^quasi-poly(nk).These bounds follow from Theorem 1.5.Source: §5 · p. 22