Linear-time Erasure List-decoding of Expander Codes
share
We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner code 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 expander code C = C(G, C_0) of length nd from approximately δδ_r nd erasures in time n ·poly(d2^r / δ), where δ and δ_r are the relative distance and the r'th generalized relative distance of 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 δ^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 δ; then we show how to improve the dependence of the running time on these parameters.
READ FULL TEXT