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