יונתן מושיוב

We study the problem of constructing (ρ,L) -list-decodable codes C ⊆ F_qⁿwith small q using 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 using O(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 the Wozencraft ensemble, achieves the Elias bound with only Ln random bits; its dual achieves the Gilbert–Varshamov bound, and both codes support quasilinear-time encoding. Our second construction uses 2nL random 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 least L(1 − R)n log₂(q) random bits to obtain rate- R codes over an alphabet of size q.