Every list-decodable code for high noise has abundant near-optimal rate puncturings

摘要

We show that any q-ary code with sufficiently good distance can be randomlypunctured to obtain, with high probability, a code that is list decodable up toradius $1 - 1/q - epsilon$ with near-optimal rate and list sizes. Our resultsimply that "most" Reed-Solomon codes are list decodable beyond the Johnsonbound, settling the long-standing open question of whether any Reed Solomoncodes meet this criterion. More precisely, we show that a Reed-Solomon code with random evaluationpoints is, with high probability, list decodable up to radius $1 - epsilon$with list sizes $O(1/epsilon)$ and rate $Omega(epsilon)$. As a secondcorollary of our argument, we obtain improved bounds on the list decodabilityof random linear codes over large fields. Our approach exploits techniques from high dimensional probability. Previouswork used similar tools to obtain bounds on the list decodability of randomlinear codes, but the bounds did not scale with the size of the alphabet. Inthis paper, we use a chaining argument to deal with large alphabet sizes.