In this paper, we give surprisingly efficient algorithms for list-decoding and testing
{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable
in the {\em high-error} regime with only a {\em constant} number of queries.
More precisely, we show that for all constants c> 0 and \gamma > 0, and for every linear code \mathcal C \subseteq \{0,1\}^N which is:
\begin{itemize}
\item {\em sparse}: |\calC| \leq N^c, and
\item {\em unbiased}: each nonzero codeword in \mathcal C has weight \in (\frac{1}{2} - N^{-\gamma}, \frac{1}{2} + N^{-\gamma}),
\end{itemize}
\mathcal C is locally testable and locally list-decodable from (\frac{1}{2} - \epsilon)-fraction worst-case errors using only \poly(\frac{1}{\epsilon}) queries to a received word. We also give {\em sub-exponential time} algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime. In particular, this yields the first sub-exponential time algorithm even for the problem of (unique) decoding random linear codes of inverse-polynomial rate from a fixed positive fraction of errors.

Earlier, Kaufman and Sudan had shown that sparse, unbiased codes
can be locally (unique) decoded and locally tested from a constant-fraction of errors, where this constant-fraction
tends to 0 as the number of codewords grows. Our results significantly strengthen their results, while also
having significantly simpler proofs.

At the heart of our algorithms is a natural ``self-correcting" operation defined on codes and received words.
This self-correcting operation transforms a code \mathcal C
with a received word w into a simpler code \mathcal C' and a related received word w', such that w is close to
\mathcal C if and only if w' is close to \mathcal C'.
Starting with a sparse, unbiased code \mathcal C and an arbitrary received word w,
a constant number of applications of the self-correcting
operation reduces us to the case of local list-decoding and testing for the {\em Hadamard code}, for which the well known
algorithms of Goldreich-Levin and Blum-Luby-Rubinfeld are available. This yields the constant-query local algorithms for
the original code \mathcal C.

Our algorithm for decoding unbiased linear codes in sub-exponential time proceeds similarly. Applying the self-correcting operation to an unbiased code \mathcal C and an arbitrary received word a
super-constant number of times, we get reduced to the problem of
{\em learning noisy parities}, for which non-trivial sub-exponential time algorithms were recently given by
Blum-Kalai-Wasserman and Feldman-Gopalan-Khot-Ponnuswami.
Our result generalizes a result of Lyubashevsky, which gave sub-exponential time algorithms for decoding random linear codes of inverse-polynomial rate, from {\em random errors}.