University of Illinois Urbana-Champaign

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

Singh, Aman

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

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

Description

Title
List decoding expander-based codes via fast approximation of expanding CSPs
Author(s)
Singh, Aman
Issue Date
2025-07-24
Director of Research (if dissertation) or Advisor (if thesis)
Granha Jeronimo, Fernando
Department of Study
Siebel School Comp & Data Sci
Discipline
Computer Science
Degree Granting Institution
University of Illinois Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
  • coding theory
  • expander codes
  • regularity
  • list decoding
Abstract
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.
Graduation Semester
2025-08
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/130060
Copyright and License Information
Copyright 2025 Aman Singh

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois