List decoding expander-based codes via fast approximation of expanding CSPs

We present near-linear time list decoding algorithms (in the block-length $n$) for expander-based code constructions. More precisely, we show that \begin{itemize} \item[(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_\delta(1), \item[(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 \exp(\poly(1/ε)), and \item[(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 \exp(\exp(\poly(1/ε))) using recent near-optimal list size bounds from~\cite{JMST25}. \end{itemize} Our results are obtained by phrasing the decoding task as an agreement CSP \cite{RWZ20,DinurHKNT19} on expander graphs and using the fast approximation algorithm for $q$-ary expanding CSPs from~\cite{Jer23}, which is based on weak regularity decomposition. Similarly to list decoding $q$-ary Ta-Shma's codes in~\cite{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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Singh, Aman

Contributors dc:contributor

• Granha Jeronimo, Fernando

• Coding Theory
• Expander Codes
• Regularity
• List Decoding

Statement dc:rights

• Copyright 2025 Aman Singh

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/130060

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F130060