2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | C.5.2 | ||
| Paper Title | Linear-Time Erasure List-Decoding of Expander Codes | ||
| Authors | Noga Ron-Zewi, University of Haifa, Israel; Mary Wootters, Stanford University, United States; Gilles Zemor, Universite de Bordeaux, France | ||
| Session | C.5: List Decoding | ||
| Presentation | Lecture | ||
| Track | Coding for Communications | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given a linear inner code $\cC_0$ of length $d$, and a $d$-regular bipartite expander graph $G$ with $n$ vertices on each side, we give an algorithm to list-decode the expander code $\cC = \cC(G, \cC_0)$ of length $nd$ from approximately $\delta \delta_r nd$ erasures in time $n \cdot \poly(d2^r / \delta)$, where $\delta$ and $\delta_r$ are the relative distance and $r$'th generalized relative distance of $\cC_0$, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately $\delta^2 nd$. To obtain our results, we show that an approach similar to that of (Hemenway, Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on $r$ and $\delta$; then we show how to improve the dependence of the running time on these parameters. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
