Key points are not available for this paper at this time.
We study the list-decodability and list-recoverability of two code ensembles: random linear codes and random Reed-Solomon codes. Inspired by the existing research about local properties of random code ensembles over small alphabets, we develop a new framework to study a similar family of properties over larger alphabets, such as in the case of Reed-Solomon codes. We introduce the notion of local coordinate-wise linear (LCL) properties, which encompasses various natural properties including list-decodability and list-recoverability. Our main contributions are twofold: (1) we establish a threshold theorem for LCL properties of random linear codes, identifying a critical rate below which these codes almost surely satisfy a given property and above which they almost surely do not; and (2) we demonstrate a reduction from random linear codes to random Reed-Solomon codes, showing that Reed-Solomon codes inherit the LCL properties of linear codes with similar rates. Our results imply that conjectures about the list-recoverability of random linear codes can be extended to random Reed-Solomon codes, potentially up to optimal bounds. Additionally, they provide a potential avenue to prove these list-recovery conjectures for random linear codes. Furthermore, our approach provides a more elementary proof of recent theorems on list-decodability for both random linear codes and random Reed-Solomon codes, avoiding reliance on complex external results.
Levi et al. (Tue,) studied this question.