Randomness-Efficient Constructions of Capacity-Achieving List-Decodable 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.