List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I

Fernando Granha Jeronimo, Aman Singh

We present near-linear time list decoding algorithms (in the block-length $n$) for expander-based code constructions. More precisely, we show that (i) For every $\hat{I}´\in (0,1)$ and $…