- Tighter Bounds on List Decodability for Alon-Edmonds-Luby (AEL) Codes
- Project Year:
2025
- REU Student (s):
Arushi Srinivasan | University of Maryland-College Park MD
- Student 1 Institution:
University of Maryland-College Park
- Project Mentor:
Shashank Srivastava
- Project Mentor Area:
DIMACS
- Project Abstract:
Alon-Edmonds-Luby (AEL) codes are combinatorial objects designed from bipartite spectral expander graphs: these are concatenated codes that offer powerful unique decoding properties with small alphabet sizes and extremely robust distance amplifications (while preserving the rate property of concatenated codes). When studying AEL codes, we follow the Hamming model: there are polynomial-time algorithms to uniquely decode an AEL codeword when e≤δ/2 (δ is the distance of the code). However, the list-decodability of AEL codes is an emerging area: following the work of Srivastava and Tulsiani, we addressed the problem of proving that when e = kδ/(k+1) as k → ∞, the singly exponential (in k) list size bounds hold but that for the realistic case of constant values of k, we can have much smaller, tight list size bounds (as opposed to the singly exponential list size bounds previously known even for local k values).
