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 continue the study of Maximally Recoverable (MR) Grid Codes initiated by Gopalan et al. [SODA 2017]. More precisely, we study codes over anm×ngrid topology with one parity check per row and column of the grid along withh≥ 1 global parity checks. Previous works have largely focused on the setting in whichm = n, where explicit constructions require field size which is exponential inn. Motivated by practical applications, we consider the regime in whichm, hare constants andnis growing. In this setting, we provide a number of new explicit constructions whose field size is polynomial inn. We further complement these results with new field size lower bounds.

The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible configuration of zeros for an MDS code. The recently emerging theory of higher order MDS codes has connected the GM-MDS theorem to other important properties of Reed-Solomon codes, including showing that Reed-Solomon codes can achieve list decoding capacity, even over fields of size linear in the message length. A few works have extended the GM-MDS theorem to other families of codes, including Gabidulin and skew polynomial codes. In this paper, we generalize all these previous results by showing that the GM-MDS theorem applies to anypolynomial code, i.e., a code where the columns of the generator matrix are obtained by evaluating linearly independent polynomials at different points. We also show that the GM-MDS theorem applies to dual codes of such polynomial codes, which is non-trivial since the dual of a polynomial code may not be a polynomial code. More generally, we show that the GM-MDS theorem also holds foralgebraic codes(and their duals) where columns of the generator matrix are chosen to be points on some irreducible variety which is not contained in a hyperplane through the origin. Our generalization has applications to constructing capacity-achieving list-decodable codes as shown in a follow-up work [2], where it is proved that randomly punctured algebraic-geometric (AG) codes achieve list-decoding capacity over constant-sized fields.

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.

The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible configuration of zeros for an MDS code. The recently emerging theory of higher order MDS codes has connected the GM-MDS theorem to other important properties of Reed-Solomon codes, including showing that Reed-Solomon codes can achieve list decoding capacity, even over fields of size linear in the message length. A few works have extended the GM-MDS theorem to other families of codes, including Gabidulin and skew polynomial codes. In this paper, we generalize all these previous results by showing that the GM-MDS theorem applies to any polynomial code, i.e., a code where the columns of the generator matrix are obtained by evaluating linearly independent polynomials at different points. We also show that the GM-MDS theorem applies to dual codes of such polynomial codes, which is non-trivial since the dual of a polynomial code may not be a polynomial code. More generally, we show that GM-MDS theorem also holds for algebraic codes (and their duals) where columns of the generator matrix are chosen to be points on some irreducible variety which is not contained in a hyperplane through the origin. Our generalization has applications to constructing capacity-achieving list-decodable codes as shown in a follow-up work [Brakensiek, Dhar, Gopi, Zhang; 2024], where it is proved that randomly punctured algebraic-geometric (AG) codes achieve list-decoding capacity over constant-sized fields.

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.

Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek et al., (2023). In later works, they were shown to be intimately connected to optimally list-decodable codes and maximally recoverable tensor codes. Therefore (explicit) constructions of higher order MDS codes over small fields is an important open problem. Higher order MDS codes are denoted by$\rm {MDS}(\ell)$where$\ell $denotes the order of generality,$\rm {MDS}(2)$codes are equivalent to the usual MDS codes. The best prior lower bound on the field size of an${[}n,k{]}$-$\rm {MDS}(\ell)$codes is$\Omega _{\ell } (n^{\ell -1})$, whereas the best known (non-explicit) upper bound is$O_{\ell } (n^{k(\ell -1)})$which is exponential in the dimension. In this work, we nearly close this exponential gap between upper and lower bounds. We show that an${[}n,k{]}$-$\rm {MDS}(3)$codes requires a field of size$\Omega _{k}(n^{k-1})$, which is close to the known upper bound. Using the connection between higher order MDS codes and optimally list-decodable codes, we show that even for a list size of 2, a code which meets the optimal list-decoding Singleton bound requires exponential field size; this resolves an open question by Shangguan and Tamo, (2020). We also give explicit constructions of${[}n,k{]}$-$\rm {MDS}(\ell)$code over fields of size$n^{(\ell k)^{O(\ell k)}}$. The smallest non-trivial case where we still do not have optimal constructions is${[}n,3{]}$-$\rm {MDS}(3)$. In this case, the known lower bound on the field size is$\Omega (n^{2})$and the best known upper bounds are$O(n^{5})$for a non-explicit construction and$O(n^{32})$for an explicit construction. In this paper, we give an explicit construction over fields of size$O(n^{3})$which comes very close to being optimal.

Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek, Gopi and Makam (IEEE Trans. Inf. Theory 2022). In later works, they were shown to be intimately connected to optimally list-decodable codes and maximally recoverable tensor codes. Therefore (explicit) constructions of higher order MDS codes over small fields is an important open problem. Higher order MDS codes are denoted by MDS(ℓ) where ℓ denotes the order of generality, MDS(2) codes are equivalent to the usual MDS codes. The best prior lower bound on the field size of an (n, k)-MDS(ℓ) codes is Ωℓ(nℓ−1), whereas the best known (non-explicit) upper bound is Oℓ(nk(ℓ−1)) which is exponential in the dimension.In this work, we nearly close this exponential gap between upper and lower bounds. We show that an (n, k)-MDS(3) codes requires a field of size Ωk(nk−1), which is close to the known upper bound. Using the connection between higher order MDS codes and optimally list-decodable codes, we show that even for a list size of 2, a code which meets the optimal list-decoding Singleton bound requires exponential field size; this resolves an open question from Shangguan and Tamo (STOC 2020).We also give explicit constructions of (n, k)-MDS(ℓ) code over fields of size ${n^{{{(\ell k)}^{O(\ell k)}}}}$. The smallest non-trivial case where we still do not have optimal constructions is (n, 3)-MDS(3). In this case, the known lower bound on the field size is Ω(n2) and the best known upper bounds are O(n5) for a non-explicit construction and O(n32) for an explicit construction. In this paper, we give an explicit construction over fields of size O(n3) which comes very close to being optimal.

Maximally Recoverable Local Reconstruction Codes (MR LRCs) are codes designed for distributed storage to provide maximum resilience to failures for a given amount of storage redundancy and locality. An (n, r, h, a, g)-MR LRC has n coordinates divided into g local groups of size r = n/g, where each local group has ‘a’ local parity checks and there are an additional ‘h’ global parity checks. Such a code can correct ‘a’ erasures in each local group and any additional erasures. Constructions of MR LRCs over small fields is desirable since field size determines the encoding and decoding efficiency in practice. In this work, we give a new construction of (n, r, h, a, g)-MR-LRCs over fields of size q = O(n)h+(g−1)a−⌈h/g⌉which generalizes a construction of Hu and Yekhanin (ISIT 2016). This improves upon state of the art when there are a small number of local groups, which is true in practical deployments of MR LRCs.

We show that a randomly chosen linear map over a finite field gives a good hash function in the $\ell_{\infty}$ sense. More concretely, consider a set $S\subset\mathbb{F}_{q}^{n}$ and a randomly chosen linear ${map}L:\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}^{t}$ with qttaken to be sufficiently smaller than $|S|$. Let USdenote a random variable distributed uniformly on S. Our main theorem shows that, with high probability over the choice of L, the random variable $L(U_{S})$ is close to uniform in the $\ell_{\infty}$ norm. In other words, every element in the range $\mathbb{F}_{q}^{t}$ has about the same number of elements in S mapped to it. This complements the widely-used Leftover Hash Lemma (LHL) which proves the analog statement under the statistical, or $\ell_{1}$, distance (for a richer class of functions) as well as prior work on the expected largest ’bucket size’ in linear hash functions [1]. By known bounds from the load balancing literature [2], our results are tight and show that linear functions hash as well as truly random function up to a constant factor in the entropy loss. Our proof leverages a connection between linear hashing and the finite field Kakeya problem and extends some of the tools developed in this area, in particular the polynomial method.

Adversarial learning of probabilistic models has recently emerged as a promising alternative to maximum likelihood. Implicit models such as generative adversarial networks (GAN) often generate better samples compared to explicit models trained by maximum likelihood. Yet, GANs sidestep the characterization of an explicit density which makes quantitative evaluations challenging. To bridge this gap, we propose Flow-GANs, a generative adversarial network for which we can perform exact likelihood evaluation, thus supporting both adversarial and maximum likelihood training. When trained adversarially, Flow-GANs generate high-quality samples but attain extremely poor log-likelihood scores, inferior even to a mixture model memorizing the training data; the opposite is true when trained by maximum likelihood. Results on MNIST and CIFAR-10 demonstrate that hybrid training can attain high held-out likelihoods while retaining visual fidelity in the generated samples.

In compressed sensing, a small number of linear measurements can be used to reconstruct an unknown signal. Existing approaches leverage assumptions on the structure of these signals, such as sparsity or the availability of a generative model. A domain-specific generative model can provide a stronger prior and thus allow for recovery with far fewer measurements. However, unlike sparsity-based approaches, existing methods based on generative models guarantee exact recovery only over their support, which is typically only a small subset of the space on which the signals are defined. We propose Sparse-Gen, a framework that allows for sparse deviations from the support set, thereby achieving the best of both worlds by using a domain specific prior and allowing reconstruction over the full space of signals. Theoretically, our framework provides a new class of signals that can be acquired using compressed sensing, reducing classic sparse vector recovery to a special case and avoiding the restrictive support due to a generative model prior. Empirically, we observe consistent improvements in reconstruction accuracy over competing approaches, especially in the more practical setting of transfer compressed sensing where a generative model for a data-rich, source domain aids sensing on a data-scarce, target domain.

Kernel principal component analysis (kPCA) learns nonlinear modes of variation in the data by nonlinearly mapping the data to kernel feature space and performing (linear) PCA in the associated reproducing kernel Hilbert space (RKHS). However, several widely-used Mercer kernels map data to a Hilbert sphere in RKHS. For such directional data in RKHS, linear analyses can be unnatural or suboptimal. Hence, we propose an alternative to kPCA by extending principal nested spheres (PNS) to RKHS without needing the explicit lifting map underlying the kernel, but solely relying on the kernel trick. It generalizes the model for the residual errors by penalizing the Lpnorm / quasi-norm to enable robust learning from corrupted training data. Our method, termed robust kernel PNS (rkPNS), relies on the Riemannian geometry of the Hilbert sphere in RKHS. Relying on rkPNS, we propose novel algorithms for dimensionality reduction and classification (with and without outliers in the training data). Evaluation on real-world datasets shows that rkPNS compares favorably to the state of the art.