2026-09-21T04:54:13Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/130060 2026-02-10 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

application/pdf en text Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2027-08-01 The student, Aman Singh, accepted the attached license on 2025-07-23 at 14:54. The student, Aman Singh, submitted this Thesis for approval on 2025-07-23 at 15:03. This Thesis was approved for publication on 2025-07-24 at 08:52. DSpace SAF Submission Ingestion Package generated from Vireo submission #22686 on 2025-10-21 at 10:06:18 List decoding expander-based codes via fast approximation of expanding CSPs Singh, Aman 2025-07-24 Granha Jeronimo, Fernando Coding Theory Expander Codes Regularity List Decoding eng 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 $\delta \in (0,1)$ and $\epsilon > 0$, there is an explicit family of good Tanner LDPC codes of (design) distance $\delta$ that is $(\delta - \epsilon, 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 $\epsilon > 0$, there is an explicit family of AEL codes of rate $R$, distance $1-R -\varepsilon$ that is $(1-R-\epsilon, O_\varepsilon(1))$ list decodable in time $\widetilde{\mathcal{O}}_{\varepsilon}(n)$ with alphabet size $\exp(\poly(1/\epsilon))$, and \item[(iii)] For every $R \in (0,1)$ and $\epsilon > 0$, there is an explicit family of AEL codes of rate $R$, distance $1-R-\varepsilon$ that is $(1-R-\epsilon, O(1/\epsilon))$ list decodable in time $\widetilde{\mathcal{O}}_{\varepsilon}(n)$ with alphabet size $\exp(\exp(\poly(1/\epsilon)))$ 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. 2025-08 Text https://hdl.handle.net/2142/130060 Copyright 2025 Aman Singh Siebel School Comp & Data Sci Computer Science University of Illinois Urbana-Champaign M.S. Thesis