Estimation of the error-correction complexity for Gallager low-density codes

It is shown that among the Gallager low-density binary codes there are codes with decoding for the correction of all errors up to multiplicity $\alpha n$ and with decoding complexity of order $n\log n$, where $n$ is the code length and $\alpha$ is a positive number.