Explicit capacity-achieving list-decodable codes or decoding up to the singleton bound using folded Reed-Solomon codes

For every 0 < R < 1 and ε > 0, we present an explicit construction of error-correcting codes of rate R that can be list decoded in polynomial time up to a fraction (1-R-ε) of errors. These codes achieve the "capacity" for decoding from adversarial errors, i.e., achieve the optimal trade-off between rate and error-correction radius. At least theoretically, this meets one of the central challenges in coding theory. Prior to this work, explicit codes achieving capacity were not known for any rate R. In fact, our codes are the first to beat the error-correction radius of 1-√R, that was achieved for Reed-Solomon (RS) codes in [9], for all rates R. (For rates R < 1/16, Parvaresh and Vardy [12] had recently improved upon the 1 - √R bound; for R → 0, their algorithm can decode a fraction 1 - O(Rlog(1/R)) of errors.) Our codes are simple to describe - they are certain folded Reed-Solomon codes, which are in fact exactly RS codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, since the codes we propose are not too far from the ones in actual use. The main insight in our work is that some carefully chosen folded RS codes are "compressed" versions of a related family of Parvaresh-Vardy codes. Further, the decoding of the folded RS codes can be reduced to list decoding the related Parvaresh-Vardy codes. The alphabet size of these folded RS codes is polynomial in the block length. This can be reduced to a constant that depends on the distance ε to capacity using ideas concerning "list recovering" and expander-based codes from [7, 8]. Concatenating the folded RS codes with suitable inner codes also gives us polytime constructible bi nary codes that can be efficiently list decoded up to the Zyablov bound.