Michael Viderman: Linear time decoding of regular expander codes

Sipser and Spielman (IEEE IT, 1996) showed that any (c,d)-regular expander code with expansion parameter > 3/4 is decodable in linear time from a constant fraction of errors. Feldman et al. (IEEE
IT, 2007) proved that expansion parameter > 2/3 + 1/3c is sufficient to correct a constant fraction of errors in 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 linear time and works for any expansion parameter > 2/3 - 1/6c. We also prove that our decoding algorithm can be executed in logarithmic time on a linear number of parallel processors.

The speaker was invited by Johan Håstad.