We introducealphabet-permutation (AP) codes, a new family of error-correcting codes defined by iteratively applying random coordinate-wise permutations to a fixed initial word. A special case recovers random additive codes and random binary linear codes, where each permutation corresponds to an additive shift over a finite field. We show that when these permutations are drawn from a suitably “mixing” distribution, the resulting code is almost surely list-recoverable with list size proportional to the inverse of the gap to capacity. Compared to any linear code, our construction achieves exponentially smaller list sizes at the same rate. Previously, only fully random codes were known to attain such parameters, requiring exponentially many random bits and offering no structure. In contrast, AP codes are structured and require only polynomially many random bits—providing the first such construction to match the list-recovery guarantees of random codes.

We study the problem of constructing (ρ,L)-list-decodable codesC⊆ Fnqwith smallqusing minimal randomness. The central goal is to generate codes of rate approaching the Elias bound, that is, rate at least 1 −h(ρ) −O(1/L), using significantly fewer random bits than required by uniformly random linear codes. Prior combinatorial constructions achieve this usingO(Ln) random bits via graph-based methods. In this work, we present two new and fully algebraic constructions that match this randomness efficiency while offering greater simplicity and structural transparency. Our first construction, a generalization of theWozencraft ensemble, achieves the Elias bound with onlyLnrandom bits; its dual achieves the Gilbert–Varshamov bound, and both codes support quasilinear-time encoding. Our second construction uses 2nLrandom bits and yields a code whose dual also achieves the Elias bound. These dual properties are critical for applications in areas such as cryptography. Our analysis proceeds by designing codes that replicate key local properties of random linear codes, allowing us to invoke known results to deduce list-decodability. As a final contribution, we prove a lower bound showing that any construction relying solely on such local approximation must use at leastL(1 −R)nlog2(q) random bits to obtain rate-Rcodes over an alphabet of sizeq.

We establish an equivalence between two important random ensembles of linear codes: random linear codes (RLCs) and random Reed-Solomon (RS) codes. Specifically, we show that these models exhibit identical behavior with respect to key combinatorial properties—such as list-decodability and list-recoverability—when the alphabet size is sufficiently large. We introduce monotone-decreasing local coordinate-wise linear (LCL) properties, a new class of properties tailored for the large alphabet regime. This class encompasses listdecodability, list-recoverability, and their average-weight variants. We develop a framework for analyzing these properties and prove a threshold theorem for RLCs: for any LCL property $\mathcal{P}$, there exists a threshold rate $R_{\mathcal{P}}$ such that RLCs are likely to satisfy $\mathcal{P}$ when R<$R_{\mathcal{P}}$ and unlikely to do so when $R\gt R_{\mathcal{P}}$. We extend this threshold theorem to random RS codes and show that they share the same threshold $R_{\mathcal{P}}$, thereby establishing the equivalence between the two ensembles and enabling a unified analysis of list-recoverability and related properties. Applying our framework, we compute the threshold rate for list-decodability, proving that both random RS codes and RLCs achieve the generalized Singleton bound. This recovers a recent result of Alrabiah, Guruswami, and Li (2023) via elementary methods. Additionally, we prove an upper bound on the list-recoverability threshold and conjecture that this bound is tight. Our approach suggests a plausible pathway for proving this conjecture and thereby pinpointing the list-recoverability parameters of both models. Indeed, following the release of a prior version of this paper, Li and Shagrithaya (2025) used our equivalence theorem to show that random RS codes are near-optimally list-recoverable.

In this work, we consider the task of generating listdecodable codes over small (say, binary) alphabets using as little randomness as possible. Specifically, we hope to generate codes achieving what we term the Elias bound, which means that they are ($\rho, L$) -list-decodable with rate$R \geq 1-h(\rho)-O(1 / L)$. A long line of work shows that uniformly random linear codes (RLCs) achieve the Elias bound: hence, we know$O\left(n^{2}\right)$random bits suffice. Prior works (Guruswami and Mosheiff, FOCS 2022; Putterman and Pyne, ITCS 2024) demonstrate that just$O(L n)$random bits suffice, via puncturing of low-bias codes. These recent constructions are essentially combinatorial, and rely (directly or indirectly) on graph expansion. We provide two new constructions, which are algebraic. Compared to prior works, our constructions are considerably simpler and more direct. Furthermore, our codes are designed in such a way that their duals are also quite easy to analyze. Our first construction which can be seen as a generalization of the celebrated Wozencraft ensemble - achieves the Elias bound and consumes$L n$random bits. Additionally, its dual code achieves the Gilbert-Varshamov bound with high probability, and both the primal and dual admit quasilinear-time encoding algorithms. The second construction consumes$2 L n$random bits and yields a code where both it and its dual achieve the Elias bound. In all of the above cases - including the prior works achieving randomness complexity$O(L n)$- the codes are designed to “approximate” RLCs. More precisely, for a given locality parameter$L$we construct codes achieving the same$L$-local properties as RLCs. This allows one to appeal to known list-decodability results for RLCs and thereby conclude that the code approximating an RLC also achieves the Elias bound (with high probability). As a final contribution, we indicate that such a proof strategy is inherently unable to generate list-decodable codes of rate$R$over$\mathbb{F}_{q}$with less than$L(1-R) n \log _{2}(q)$bits of randomness.

We study list-recoverability of random linear codes over small fields, both from errors and from erasures. We consider codes of rate ε-close to capacity, and aim to bound the dependence of the output list sizeLon ε, the input list size ℓ, and the alphabet sizeq. Prior to our work, the best upper bound wasL=qO(ℓ/ε)(Zyablov and Pinsker, Prob. Per. Inf. 1981). Previous work has identified cases in whichlinearcodes provably perform worse than non-linear codes with respect to list-recovery. While there exist non-linear codes that achieveL=O(ℓ/ε), we know thatL≥ ℓΩ(1/ε)is necessary for list recovery from erasures over fields of small characteristic, and for list recovery from errors over large alphabets. We show that in other relevant regimes there is no significant price to pay for linearity, in the sense that we get the correct dependence on the gap-to-capacity ε and go beyond the Zyablov– Pinsker bound for the first time. Specifically, whenqis constant and ε approaches zero, • For list-recovery from erasures overprime fields, we show thatL≤C1/ε. By prior work, such a result cannot be obtained for low-characteristic fields. • For list-recovery from errors over arbitrary fields, we prove thatL≤C2/ε. Above,C1andC2depend on the decoding radius, input list size, and field size. We provide concrete bounds on the constants above, and the upper bounds onLimprove upon the Zyablov– Pinsker bound wheneverq≤ 2(1/ε)cfor some small universal constantc> 0.

The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $ε^2$ has relative distance at least $\frac{1}{2} - O(ε)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters. One hope to derandomize the Gilbert--Varshamov construction is with code concatenation: We begin with a (hopefully explicit) outer code ${C}_\mathrm{out}$ over a large alphabet, and concatenate that with a small binary random linear code ${C}_\mathrm{in}$. It is known that when we use independent small codes for each coordinate, then the result lies on the GV bound with high probability, but this still uses a lot of randomness. In this paper, we consider the question of whether code concatenation with a single random linear inner code ${C}_\mathrm{in}$ can lie on the GV bound; and if so what conditions on ${C}_\mathrm{out}$ are sufficient for this. We show that first, there do exist linear outer codes ${C}_\mathrm{out}$ that are "good" for concatenation in this sense (in fact, most linear codes codes are good). We also provide two sufficient conditions for ${C}_\mathrm{out}$, so that if ${C}_\mathrm{out}$ satisfies these, ${C}_\mathrm{out}\circ {C}_\mathrm{in}$ will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes ${C}_\mathrm{out}$.

We show that Gallager's ensemble of low-density parity-check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue toward truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list-decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords and include list-decodability, list-recoverability, and average-radius list-decodability. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property $\mathcal{P}$, there is some $R^*$ so that random linear codes of rate slightly less than $R^*$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^*$, with high probability, do not. We also give a characterization of the threshold rate $R^*$.

Random subspaces X of ℝⁿ of dimension proportional to n are, with high probability, well-spread with respect to the 𝓁₂-norm. Namely, every nonzero x ∈ X is "robustly non-sparse" in the following sense: x is ε ‖x‖₂-far in 𝓁₂-distance from all δ n-sparse vectors, for positive constants ε, δ bounded away from 0. This "𝓁₂-spread" property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and corresponds to X being a Euclidean section of the 𝓁₁ unit ball. Explicit 𝓁₂-spread subspaces of dimension Ω(n), however, are unknown, and the best known explicit constructions (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of certain sparse matrices. Motivated by this, we study the spread properties of the kernels of sparse random matrices. We prove that with high probability such subspaces contain vectors x that are o(1)⋅‖x‖₂-close to o(n)-sparse with respect to the 𝓁₂-norm, and in particular are not 𝓁₂-spread. This is strikingly different from the case of random LDPC codes, whose distance is asymptotically almost as good as that of (dense) random linear codes. On the other hand, for p < 2 we prove that such subspaces are 𝓁_p-spread with high probability. The spread property of sparse random matrices thus exhibits a threshold behavior at p = 2. Our proof for p < 2 moreover shows that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the 𝓁_p norm, and in fact this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the 𝓁₁ norm [Berinde et al., 2008]. Instantiating this with suitable explicit expanders, we obtain the first explicit constructions of 𝓁_p-RIP matrices for 1 ≤ p < p₀, where 1 < p₀ < 2 is an absolute constant.

Random linear codes are a workhorse in coding theory, and are used to show the existence of codes with the best known or even near-optimal trade-offs in many noise models. However, they have little structure besides linearity, and are not amenable to tractable error-correction algorithms. In this work, we prove a general derandomization result applicable to random linear codes. Namely, in settings where the coding-theoretic property of interest is “local” (in the sense of forbidding certain bad configurations involving few vectors–code distance and list-decodability being notable examples), one can replace random linear codes (RLCs) with a significantly derandomized variant with essentially no loss in parameters. Specifically, instead of randomly sampling coordinates of the (long) Hadamard code (which is an equivalent way to describe RLCs), one can randomly sample coordinates of any code with low bias. Over large alphabets, the low bias requirement can be weakened to just large distance. Furthermore, large distance suffices even with a small alphabet in order to match the current best known bounds for RLC list-decodability. In particular, by virtue of our result, all current (and future) achievability bounds for list-decodability of random linear codes extend automatically to random puncturings of any low-bias (or large alphabet) “mother” code. We also show that our punctured codes emulate the behavior of RLCs on stochastic channels, thus giving a derandomization of RLCs in the context of achieving Shannon capacity as well. Thus, we have a randomness-efficient way to sample codes achieving capacity in both worst-case and stochastic settings that can further inherit algebraic or other algorithmically useful structural properties of the mother code. This is an extended abstract. The full version is available at https://arxiv.org/abs/2109.11725.

A family of error-correcting codes is list-decodable from error fraction$p$if, for every code in the family, the number of codewords in any Hamming ball of fractional radius$p$is less than some integer$L$. It is said to be list-recoverable for input list size$\ell $if for every sufficiently large subset of at least$L$codewords, there is a coordinate where the codewords take more than$\ell $values. In this work, we study the list size ofrandom linear codesfor both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below$q$is the alphabet size, and$ \varepsilon > 0$is the gap to capacity). (1) A random linear code of rate$1 - \log _{q}(\ell) - \varepsilon $requires list size$L \ge \ell ^{\Omega (1/ \varepsilon)}$for list-recovery from input list size$\ell $. (2) A random linear code of rate$1 - h_{q}(p) - \varepsilon $requires list size$L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $for list-decoding from error fraction$p$. (3) A randombinarylinear code of rate$1 - h_{2}(p) - \varepsilon $is list-decodable fromaverageerror fraction$p$with list size with$L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018).

Suppose that$\mathcal {P}$is a property that may be satisfied by a random code$C \subset \Sigma ^{n}$. For example, for some$p \in (0,1)$,$\mathcal {P}$might be the property that there exist three elements of$C$that lie in some Hamming ball of radius$pn$. We say that$R^{\ast}$is thethreshold ratefor$\mathcal {P}$if a random code of rate$R^{\ast} + \varepsilon $is very likely to satisfy$\mathcal {P}$, while a random code of rate$R^{\ast} - \varepsilon $is very unlikely to satisfy$\mathcal {P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably “symmetric.” For properties in this class, we show that the threshold rate is in factequalto the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property$\mathcal {P}$above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates forlist-recoveryin general.

We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple (σ1, …, σd) of permutations on \{1, \ldots, n\}, and one wishes to determine whether this tuple satisfies a certain system of relations E, or is far from every tuple that satisfies E. If this computational problem can be solved by querying only a small number of entries of the given permutations, we say that E is testable. For example, when d=2 and E consists of the single relation \mathrm{XY}= \mathrm{YX}, this corresponds to testing whether σ1σ2=σ2σ1, where σ1σ2and σ2σ1denote composition of permutations. We define a collection of graphs, naturally associated with the system E, that encodes all the information relevant to the testability of E. We then prove two theorems that provide criteria for testability and non-testability in terms of expansion properties of these graphs. By virtue of a deep connection with group theory, both theorems are applicable to wide classes of systems of relations. In addition, we formulate the well-studied group-theoretic notion of stability in permutations as a special case of the testa-bility notion above, interpret all previous works on stability as testability results, survey previous results on stability from a computational perspective, and describe many directions for future research on stability and testability. This is an extended abstract. The full version is available at https://arxiv.org/abs/2011.05234. All references beyond Sections I and II refer to the full version.

Suppose that 𝒫 is a property that may be satisfied by a random code C ⊂ Σⁿ. For example, for some p ∈ (0,1), 𝒫 might be the property that there exist three elements of C that lie in some Hamming ball of radius pn. We say that R^* is the threshold rate for 𝒫 if a random code of rate R^* + ε is very likely to satisfy 𝒫, while a random code of rate R^* - ε is very unlikely to satisfy 𝒫. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably "symmetric." For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property 𝒫 above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property P, there is some R* so that random linear codes of rate slightly less than R* satisfy P with high probability, while random linear codes of rate slightly more than R* with high probability do not. We also give a characterization of the threshold rate R*. This is an extended abstract. The full version is available at https://arxiv.org/abs/1909.06430