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.

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.