Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR08-054 | 13th May 2008 00:00

#### Concatenated codes can achieve list-decoding capacity

TR08-054
Authors: Venkatesan Guruswami, Atri Rudra
Publication: 19th May 2008 05:09
We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of rate at least $1-H(\rho)-\epsilon$ that are (combinatorially) list-decodable up to a $\rho$ fraction of errors. (The best possible rate, aka list-decoding capacity, for such codes is $1-H(\rho)$, and is achieved by random codes.) A similar result, with better list size guarantees, holds when the outer code is also randomly chosen. Our methods and results extend to the case when the alphabet size is any fixed prime power $q \ge 2$.