We present an explicit construction of codes that can be list decoded
from a fraction $(1-\eps)$ of errors in sub-exponential time and which
have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal
rate of $\Omega(\eps)$, and is the first sub-exponential complexity
construction to beat the rate of $O(\eps^2)$ achieved by Reed-Solomon
or algebraic-geometric codes. Beating this quadratic rate with
{\em polynomial} decoding complexity remains one of the central open
questions in the area of list decoding, and this work lends some hope
to the eventual resolution of this question.

Our construction is based on recent extractor constructions with very
good seed length due to Ta-Shma, Zuckerman, and Safra. While the ``standard'' way of viewing extractors as codes cannot beat the $O(\eps^2)$ rate barrier due to the $2 \log (1/\eps)$ lower bound on seed length for extractors, we use such extractor codes as a component in certain expander-based construction schemes to get our result. The $O(\eps^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 conceptual message from our work is that good strong extractors
for low min-entropies will lead to 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 extractors, as well as by importing
non-trivial techniques from the extractor world in reasoning about and
constructing codes