When can an expander code correct $\mathrm{\Omega }(n)$ errors in $O(n)$ time?

Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph $G$ together with a linear inner code $C_0$. Expander codes are Tanner codes whose defining bipartite graph $G$ has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that $\delta$ and $d_0$ must satisfy, so that $\mathit{\text{every}}$ bipartite expander $G$ with vertex expansion ratio $\delta$ and $\mathit{\text{every}}$ linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $\mathrm{\Omega }(n)$ errors in $O(n)$ time? For $C_0$ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT’96) showed that $\delta >3\mathrm{/}4$ is sufficient; later Viderman (ACM-TOCT’13) improved this to $\delta >2\mathrm{/}3-\mathrm{\Omega }(1)$ and he also showed that $\delta >1\mathrm{/}2$ is necessary. For general linear code $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT’18) showed that $d_0=\mathrm{\Omega }(c{\delta }^{-2})$ is sufficient, where $c$ is the left-degree of $G$. In this paper, we give a near-optimal solution to the above question for general $C_0$ by showing that $\delta d_0>3$ is sufficient and $\delta d_0>1$ is necessary, thereby also significantly improving Dowling-Gao’s result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.