Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR13-140 | 8th October 2013 02:05

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

TR13-140
Authors: Atri Rudra, Mary Wootters
Publication: 8th October 2013 09:27
Keywords:

Abstract:

We show that any $q$-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius $1 - 1/q - \epsilon$ with near-optimal rate and list sizes.

Our results imply that most" Reed-Solomon codes are list decodable beyond the Johnson bound, settling the long-standing open question of whether *any* Reed Solomon codes meet this criterion. More precisely, we show that a Reed-Solomon code with random evaluation points is, with high probability, list decodable up to radius $1 - \epsilon$ with list sizes $O(1/\epsilon)$ and rate $\widetilde{\Omega}(\epsilon)$. As a second corollary of our argument, we obtain improved bounds on the list decodability of random linear codes over large fields.

Our approach exploits techniques from high dimensional probability. Previous work used similar tools to obtain bounds on the list decodability of random linear codes, but the bounds did not scale with the size of the alphabet. In this paper, we use a chaining argument to deal with large alphabet sizes.

ISSN 1433-8092 | Imprint