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 errors. These codes achieve the ``capacity'' for decoding from {\em adversarial} errors, i.e., achieve ... more >>>

We give a polynomial time construction of binary codes with the best currently known trade-off between rate and error-correction radius. Specifically, we obtain linear codes over fixed alphabets that can be list decoded in polynomial time up to the so called Blokh-Zyablov bound. Our work builds upon (Guruswami-Rudra STOC06) where ... more >>>

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 ... more >>>