Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-058 | 18th July 2011 17:28

Linear time decoding of regular expander codes

Revision #1
Authors: Michael Viderman
Accepted on: 18th July 2011 17:28
Downloads: 1760
Keywords:

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.

Paper:

TR11-058 | 15th April 2011 12:27

Linear time decoding of regular expander codes

TR11-058
Authors: Michael Viderman
Publication: 15th April 2011 13:13
Downloads: 2880
Keywords:

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

ISSN 1433-8092 | Imprint