Jonathan Mosheiff

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 P, there exists a threshold rate RP such that RLCs are likely to satisfy P when R<RP and unlikely to do so when R> RP. We extend this threshold theorem to random RS codes and show that they share the same threshold RP, 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.