ECCC-Report TR20-013https://eccc.weizmann.ac.il/report/2020/013Comments and Revisions published for TR20-013en-usMon, 24 May 2021 21:23:04 +0300
Revision 1
| Linear-time Erasure List-decoding of Expander Codes |
Noga Ron-Zewi,
Mary Wootters,
Gilles Z\'{e}mor
https://eccc.weizmann.ac.il/report/2020/013#revision1We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an 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 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 the $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 and Wootters, \emph {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.Mon, 24 May 2021 21:23:04 +0300https://eccc.weizmann.ac.il/report/2020/013#revision1
Paper TR20-013
| Linear-time Erasure List-decoding of Expander Codes |
Noga Ron-Zewi,
Mary Wootters,
Gilles Z\'{e}mor
https://eccc.weizmann.ac.il/report/2020/013We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an 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 the $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 and Wootters, \emph {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.Tue, 18 Feb 2020 17:44:18 +0200https://eccc.weizmann.ac.il/report/2020/013