Decoding Complexity of Low-Density Codes For Transmission in a Channel with Erasures

It is proved that low density codes of length $n$ exist with a decoding that corrects all erasures up to multiplicity on with a complexity of order $n\ln n$. It is shown that the ratio of $\alpha n$ to the code distance corresponding to the Varshamov–Gilbert bound has a lower bound varying from 0.33 to 0.66 as the transmission rate is increased from 0 to 1.