Error exponents of expander codes under linear-complexity decoding

A class of codes is said to reach capacity $cC$ of the binary symmetric channel if for any rate $R0$ there is a sufficiently large $N$ such that codes of length $ge N$ and rate $R$ from this class provide error probability of decoding at most $varepsilon$, under some decoding algorithm. 

The study of the error probability of expander codes was initiated in Barg and Z{'e}mor (2002), where it was shown that they attain capacity of the binary symmetric channel under a linear- time iterative decoding with error probability falling exponentially with code length $N$. 

In this work we study variations on the expander code construction and focus on the most important region of code rates, close to the channel capacity. For this region we estimate the decrease rate (the error exponent) of error probability of decoding for randomized ensembles codes. The resulting estimate gives a substantial improvement of previous results for expander codes and some other explicit code families.