Motivated by recent developments in coding theory, particular in list-decoding, we introduce a new error model which we call semi-adversarial errors. This error model bridges between fully random errors and fully adversarial errors by allowing some symbols of a message to be corrupted by an adversary while others are replaced with uniformly random symbols. As our main quest, we seek to understand optimal efficient unique decoding algorithms in the semi-adversarial model. For interleaved Reed--Solomon (IRS), folded Reed--Solomon (FRS) and univariate multiplicity codes, we design decoding algorithms running in near-linear time for most mixtures of random and adversarial errors. Our analysis matches the information-theoretic optimum for semi-adversarial errors. Our algorithm for interleaved Reed--Solomon codes is an improved implementation of the decoding algorithm by Bleichenbacher--Kiayias--Yung (BKY) for fully random errors. We use a novel monomial-tracking technique to analyze its performance in this new semi-adversarial errors. Inspired by the BKY algorithm, we use novel interpolations to extend our approach to the settings of folded Reed--Solomon and multiplicity codes, resulting in fast algorithms for unique decoding against semi-adversarial errors. Our new decoders for FRS and multiplicity codes replace the sophisticated root-finding step in traditional algorithms, such as the Guruswami--Wang algorithm, with a straightforward polynomial long division. Analysis of these algorithms requires more robust monomial-tracking arguments than IRS codes.

In coding theory, the problem of list recovery asks one to find all codewords c of a given code C which such that at least 1−ρ fraction of the symbols of c lie in some predetermined set of ℓ symbols for each coordinate of the code. A key question is bounding the maximum possible list size L of such codewords for the given code C.

In coding theory, a common question is to understand the threshold rates of various local properties of codes, such as their list decodability and list recoverability. A recent work Levi, Mosheiff, and Shagrithaya (FOCS 2025) gave a novel unified framework for calculating the threshold rates of local properties for random linear and random Reed–Solomon codes.

In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - with linear-sized alphabets. More precisely, we prove that, for any ε > 0 and positive integers n and k, with high probability, random Reed-Solomon codes of length n and dimension k can correct (1-ε)n-2k+1 adversarial insdel errors over alphabets of size n+2^{poly(1/ε)}k. This significantly improves upon the alphabet size demonstrated in the work of Con, Shpilka, and Tamo (IEEE TIT, 2023), who showed the existence of Reed-Solomon codes with exponential alphabet size Õ(binom(n,2k-1)²) precisely achieving the half-Singleton bound. Our methods are inspired by recent works on list-decoding Reed-Solomon codes. Brakensiek-Gopi-Makam (STOC 2023) showed that random Reed-Solomon codes are list-decodable up to capacity with exponential-sized alphabets, and Guo-Zhang (FOCS 2023) and Alrabiah-Guruswami-Li (STOC 2024) improved the alphabet-size to linear. We achieve a similar alphabet-size reduction by similarly establishing strong bounds on the probability that certain random rectangular matrices are full rank. To accomplish this in our insdel context, our proof combines the random matrix techniques from list-decoding with structural properties of Longest Common Subsequences.

Peer Reviewed

The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally recoverable (MR) tensor codes, codes with optimal list-decoding guarantees, and codes with constrained generator matrices (as in the GM-MDS theorem). By proving these equivalences, Brakensiek-Gopi-Makam ([1]) showed the existence of optimally list-decodable Reed-Solomon codes over exponential sized fields. Building on this, recent breakthroughs by Guo-Zhang ([2]) and Alrabiah-Guruswami-Li ([3]) have shown that randomly punctured Reed-Solomon codes achieve list-decoding capacity (which is a relaxation of optimal list-decodability) over linear size fields. We extend these works by developing a formal theory ofrelaxed higher order MDS codes. In particular, we show that there are two inequivalent relaxations which we calllowerandupperrelaxations. The lower relaxation is equivalent to relaxed optimal list-decodable codes and the upper relaxation is equivalent to relaxed MR tensor codes with a single parity check per column. We then generalize the techniques of Guo-Zhang and Alrabiah- Guruswami-Li to show that both these relaxations can be constructed by randomly puncturing suitable algebraic-geometric codes overconstant sizefields. For this, we crucially use the generalized GM-MDS theorem for polynomial codes recently proved by Brakensiek-Dhar-Gopi ([4]). We obtain the following corollaries from our main result: • Randomly punctured algebraic-geometric codes of rate R are list-decodable up to radiusL/L+1 (1 −R− ϵ) with list sizeLover fields of size exp(O(L/ϵ)). In particular, they achieve list-decoding capacity with list sizeO(1/ϵ) and field size exp(O(1/ϵ2)). Prior to this work, AG codes were not even known to achieve list-decoding capacity. • By randomly puncturing algebraic-geometric codes, we can construct relaxed MR tensor codes with a single parity check per column overconstant-sizedfields, whereas (non-relaxed) MR tensor codes require exponential field size.

Gabidulin codes, serving as the rank-metric counterpart of Reed-Solomon codes, constitute an important class of maximum rank distance (MRD) codes. However, unlike the fruitful positive results about the list decoding of Reed-Solomon codes, results concerning the list decodability of Gabidulin codes in the rank metric are all negative so far. For example, in contrast to Reed-Solomon codes, which are always list decodable up to the Johnson bound in the Hamming metric, Raviv and Wachter-Zeh (IEEE TIT, 2016 and 2017) constructed a class of Gabidulin codes that are not even combinatorially list decodable beyond the unique decoding radius in the rank metric. Proving the existence of Gabidulin codes with good combinatorial list decodability in the rank metric has remained a long-standing open problem. In this paper, we resolve the aforementioned open problem by showing that, with high probability, random Gabidulin codes over sufficiently large alphabets attain the optimal generalized Singleton bound for list decoding in the rank metric. In particular, they achieve list decoding capacity in the rank metric. Our work is significantly influenced by the recent break-throughs in the combinatorial list decodability of Reed-Solomon codes, especially the work by Brakensiek, Gopi, and Makam (STOC 2023). Our major conceptual and technical contributions, which may hold independent interest, consist of the following: (1) We initiate the study of “higher order MRD codes” and provide a novel unified theory, which runs parallel to the theory of “higher order MDS codes” developed by Brakensiek, Gopi, and Makam. (2) We prove a natural analog of the GM-MDS theorem, proven by Lovett (FOCS 2018) and Yildiz and Hassibi (IEEE TIT, 2019), which we call the GM-MRD theorem. In particular, our GMMRD theorem for Gabidulin codes is strictly stronger than the GM-MDS theorem for Gabidulin codes proven by Yildiz and Hassibi.

The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally recoverable (MR) tensor codes, codes with optimal list-decoding guarantees, and codes with constrained generator matrices (as in the GM-MDS theorem). By proving these equivalences, Brakensiek-Gopi-Makam showed the existence of optimally list-decodable Reed-Solomon codes over exponential sized fields. Building on this, recent breakthroughs by Guo-Zhang and Alrabiah-Guruswami-Li have shown that randomly punctured Reed-Solomon codes achieve list-decoding capacity (which is a relaxation of optimal list-decodability) over linear size fields. We extend these works by developing a formal theory of relaxed higher order MDS codes. In particular, we show that there are two inequivalent relaxations which we call lower and upper relaxations. The lower relaxation is equivalent to relaxed optimal list-decodable codes and the upper relaxation is equivalent to relaxed MR tensor codes with a single parity check per column. We then generalize the techniques of Guo-Zhang and Alrabiah-Guruswami-Li to show that both these relaxations can be constructed over constant size fields by randomly puncturing suitable algebraic-geometric codes. For this, we crucially use the generalized GM-MDS theorem for polynomial codes recently proved by Brakensiek-Dhar-Gopi. We obtain the following corollaries from our main result: Randomly punctured algebraic-geometric codes of rate R are list-decodable up to radius L/L+1(1−R−є) with list size L over fields of size exp(O(L/є)). In particular, they achieve list-decoding capacity with list size O(1/є) and field size exp(O(1/є2)). Prior to this work, AG codes were not even known to achieve list-decoding capacity. By randomly puncturing algebraic-geometric codes, we can construct relaxed MR tensor codes with a single parity check per column over constant-sized fields, whereas (non-relaxed) MR tensor codes require exponential field size.

This paper shows that, with high probability, randomly punctured Reed-Solomon codes over fields of polynomial size achieve the list decoding capacity. More specifically, we prove that for any $\varepsilon \gt 0$ and $R \in(0,1)$, with high probability, randomly punctured Reed-Solomon codes of block length n and rate R are $(1-R-\varepsilon, O(1 / \varepsilon))$ list decodable over alphabets of size at least $2^{\text {poly }(1 / \varepsilon)} n^{2}$. This extends the recent breakthrough of Brakensiek, Gopi, and Makam (STOC 2023) that randomly punctured Reed-Solomon codes over fields of exponential size attain the generalized Singleton bound of Shangguan and Tamo (STOC 2020).