{"ID":2874299,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.05203","arxiv_id":"2509.05203","title":"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 $δ\\in (0,1)$ and $ε\u003e 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 $ε\u003e 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 $ε\u003e 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.","short_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 $δ\\in (0,1)$ and $ε\u003e 0$, there is an explicit family of good Tanner LDPC codes of (design) distance $δ$ that is $(δ- ε, O_\\varepsilon(1))$ list decodable in ti...","url_abs":"https://arxiv.org/abs/2509.05203","url_pdf":"https://arxiv.org/pdf/2509.05203v1","authors":"[\"Fernando Granha Jeronimo\",\"Aman Singh\"]","published":"2025-09-05T16:07:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.IT\"]","methods":"[]","has_code":false}