Local Properties of Reed-Solomon Codes and Random Linear Codes
<|reference_start|>Local Properties of Reed-Solomon Codes and Random Linear Codes: 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 threefold: (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; (2) we use this framework to prove that random linear codes are essentially optimally list-decodable and list-recoverable in the large alphabet regime; and (3) 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. We conclude that random Reed-Solomon codes, with alphabet size that may be as small as linear in the code length, are also optimally list-decodable and list-recoverable.   For list-recovery, our results about both ensembles constitute a significant leap from the best previously known bounds. For list-decodability, we recover recent theorems via a more direct approach, avoiding reliance on complex external results.<|reference_end|>
@article{levi2024random,
    title={Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent},
    author={Matan Levi, Jonathan Mosheiff and Nikhil Shagrithaya},
    journal={arXiv preprint arXiv:2406.02238},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.02238},
    primaryClass={cs.IT math.IT}
}