
























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 $δ\in (0,1)$ and $ε> 0$, there is an explicit family of good Tanner LDPC codes of (design) distance $δ$ that is $(δ- ε, O_\varepsilon(1))$ list decodable in time $\widetilde{\mathcal{O}}_{\varepsilon}(n)$ with alphabet size $O_δ(1)$, (ii) For every $R \in (0,1)$ and $ε> 0$, there is an explicit family of AEL codes of rate $R$, distance $1-R -\varepsilon$ that is $(1-R-ε, O_\varepsilon(1))$ list decodable in time $\widetilde{\mathcal{O}}_{\varepsilon}(n)$ with alphabet size $\text{exp}(\text{poly}(1/ε))$, and (iii) For every $R \in (0,1)$ and $ε> 0$, there is an explicit family of AEL codes of rate $R$, distance $1-R-\varepsilon$ that is $(1-R-ε, O(1/ε))$ list decodable in time $\widetilde{\mathcal{O}}_{\varepsilon}(n)$ with alphabet size $\text{exp}(\text{exp}(\text{poly}(1/ε)))$ 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。