Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-140 | 8th October 2013 02:05

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


Authors: Atri Rudra, Mary Wootters
Publication: 8th October 2013 09:27
Downloads: 3961


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