期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove the existence of Reed-Solomon codes of any desired rate R(01) that are combinatorially list-decodable up to a radius approaching 1−R , which is the information-theoretic limit. This is established by starting with the full-length [qk]q Reed-Solomon code over a field Fq that is polynomially larger than the desired dimension k, and "puncturing" it by including kR randomly chosen codeword positions. Our puncturing result is more general and applies to any code with large minimum distance: we show that a random rate R puncturing of an Fq-linear "mother" code whose relative distance is close enough to 1−1q is list-decodable up to a radius approaching the q-ary list-decoding capacity bound hq−1(1−R) . In fact, for large q, or under a stronger assumption of low-bias of the mother-code, we prove that the threshold rate for list-decodability with a specific list-size (and more generally, any "local" property) of the random puncturing approaches that of fully random linear codes. Thus, all current (and future) list-decodability bounds shown for random linear codes extend automatically to random puncturings of any low-bias (or large alphabet) code. This can be viewed as a general derandomization result applicable to random linear codes. To obtain our conclusion about Reed-Solomon codes, we establish some hashing properties of field trace maps that allow us to reduce the list-decodability of RS codes to its associated trace (dual-BCH) code, and then apply our puncturing theorem to the latter. Our approach implies, essentially for free, optimal rate list-recoverability of punctured RS codes as well.
