Better extractors for better codes?

We present an explicit construction of codes that can be list decoded from a fraction (1-ε) of errors in sub-exponential time and which have rate ε/log O(1) (1/ε). This comes close to the optimal rate of Ω(ε), and is the first sub-exponential complexity construction to beat the rate of ε 2 achieved by Reed-Solomon or algebraic-geometric codes. Our construction is based on recent extractor constructions with very good seed length [17]. While the "standard" way of viewing extractors as codes (as in [16]) cannot beat the O(ε 2 ) rate barrier due to the 2 log (1/ε) lower bound on seed length for extractors, we use such extractor codes as a component in a well-known expander-based construction scheme to get our result. The O(ε 2 ) rate barrier also arises if one argues about list decoding using the minimum distance (via the so-called Johnson bound) --- so this also gives the first explicit construction that "beats the Johnson bound" for list decoding from errors.The main message from our work is perhaps conceptual, namely that good strong extractors for low min-entropies will yield near-optimal list decodable codes. Given all the progress that has been made on extractors, we view this as an optimistic avenue to look for better list decodable codes, both by looking for better explicit extractor constructions, as well as by importing non-trivial techniques from the extractor world in reasoning about and constructing codes.

Authors

• Venkatesan Guruswami

Keywords

• list decoding
• error-correcting codes
• expander graphs
• randomness extractors
• pseudorandomness