  We present error-correcting codes that achieve the information-theoretically
best possible trade-off between the rate and error-correction radius.
Specifically, for every $0 < R < 1$ and $\eps> 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-\eps)$ of {\em worst-case} errors. At
least theoretically, this meets one of the central challenges in algorithmic
coding theory.
  Our codes are simple to describe: they are {\em folded Reed-Solomon codes},
which are in fact {\em exactly} Reed-Solomon (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, and in fact
our methods directly yield better decoding algorithms for RS codes when errors
occur in {\em phased bursts}.
  The alphabet size of these folded RS codes is polynomial in the block length.
We are able to reduce this to a constant (depending on $\eps$) using ideas
concerning ``list recovery'' and expander-based codes from
\cite{GI-focs01,GI-ieeejl}. Concatenating the folded RS codes with suitable
inner codes also gives us polynomial time constructible binary codes that can
be efficiently list decoded up to the Zyablov bound, i.e., up to twice the
radius achieved by the standard GMD decoding of concatenated codes.
