2013/10/07 by Atri Rudra, Mary Wootters, Rudra, Atri +1 · 1 citation
Computer Science · Engineering · #Coding theory and cryptography #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1310.1891
openalex publication_date 2013/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that any q-ary code with sufficiently good distance can be randomly\npunctured to obtain, with high probability, a code that is list decodable up to\nradius 1 - 1/q - \ε with near-optimal rate and list sizes. Our results\nimply that "most" Reed-Solomon codes are list decodable beyond the Johnson\nbound, settling the long-standing open question of whether any Reed Solomon\ncodes meet this criterion.\n More precisely, we show that a Reed-Solomon code with random evaluation\npoints is, with high probability, list decodable up to radius 1 - \ε\nwith list sizes O(1/\ε) and rate \Ω(\ε). As a second\ncorollary of our argument, we obtain improved bounds on the list decodability\nof random linear codes over large fields.\n Our approach exploits techniques from high dimensional probability. Previous\nwork used similar tools to obtain bounds on the list decodability of random\nlinear codes, but the bounds did not scale with the size of the alphabet. In\nthis paper, we use a chaining argument to deal with large alphabet sizes.\n