Linear-Time Erasure List-Decoding of Expander Codes

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an inner code ${\mathcal {C}}_{0}$ of length $d$ , and a $d$ -regular bipartite expander graph $G$ with $n$ vertices on each side, we give an algorithm to list-decode the code ${\mathcal {C}}= {\mathcal {C}}(G, {\mathcal {C}}_{0})$ of length $nd$ from approximately $\delta \delta _{r} nd$ erasures in time $n \cdot \mathrm {poly} (d2^{r} / \delta)$ , where $\delta $ and $\delta _{r}$ are the relative distance and the $r$ ’th generalized relative distance of ${\mathcal {C}}_{0}$ , respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately $\delta ^{2}~nd$ . To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation , 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on $r$ and $\delta $ ; then we show how to improve the dependence of the running time on these parameters.