Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007) proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of errors in \emph{polynomial time} using LP decoding.

In this work we give a simple combinatorial algorithm that achieves even better parameters. In particular, our algorithm runs in \emph{linear time} and works for any expansion parameter $> \frac{2}{3} - \frac{1}{6c}$.
We also prove that our decoding algorithm can be executed in logarithmic time on a linear number of parallel processors.

(1) some typos were fixed
(2) It was shown that the main decoding algorithm can be executed in logarithmic time on a linear number of processors.

Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)
proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of errors in \emph{polynomial time} using LP decoding.

In this work we give a simple combinatorial algorithm that achieves even better parameters. In particular, our algorithm runs in \emph{linear time} and works for any expansion parameter $> \frac{2}{3} - \frac{1}{6c}$.