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

Abstract

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 $\hat{I}\mu >0$, there is an explicit family of good Tanner LDPC codes of (design) distance $\hat{I}´$ that is $(\hat{I}´-\hat{I}\mu ,O_{\epsilon }(1))$ list decodable in time ${\tilde{\mathcal{O}}}_{\epsilon }(n)$ with alphabet size $O_{\hat{I}}´(1)$, (ii) For every $R\in (0,1)$ and $\hat{I}\mu >0$, there is an explicit family of AEL codes of rate $R$, distance $1-R-\epsilon$ that is $(1-R-\hat{I}\mu ,O_{\epsilon }(1))$ list decodable in time ${\tilde{\mathcal{O}}}_{\epsilon }(n)$ with alphabet size $\text{exp}(\text{poly}(1/\hat{I}\mu ))$, and (iii) For every $R\in (0,1)$ and $\hat{I}\mu >0$, there is an explicit family of AEL codes of rate $R$, distance $1-R-\epsilon$ that is $(1-R-\hat{I}\mu ,O(1/\hat{I}\mu ))$ list decodable in time ${\tilde{\mathcal{O}}}_{\epsilon }(n)$ with alphabet size $\text{exp}(\text{exp}(\text{poly}(1/\hat{I}\mu )))$ using recent near-optimal list size bounds from [JMST25]. Our results are obtained by phrasing the decoding task as an agreement CSP [RWZ20,DHKNT19] on expander graphs and using the fast approximation algorithm for $q$-ary expanding CSPs from [Jer23], which is based on weak regularity decomposition [JST21,FK96]. Similarly to list decoding $q$-ary Ta-Shma's codes in [Jer23], we show that it suffices to enumerate over assignments that are constant in each part (of the constantly many) of the decomposition in order to recover all codewords in the list.