__
Revision #1 to TR11-058 | 18th July 2011 17:28
__
#### Linear time decoding of regular expander codes

**Abstract:**
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.

**Changes to previous version:**
(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.

__
TR11-058 | 15th April 2011 12:27
__

#### Linear time decoding of regular expander codes

**Abstract:**
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}$.