论文标题
线性时间擦除列表编码的扩展器代码
Linear-time Erasure List-decoding of Expander Codes
论文作者
论文摘要
我们为扩展器代码提供了一个线性时间擦除列表编码算法。更确切地说，令$ r> 0 $为任何整数。 Given an inner code $C_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 $C = C(G, C_0)$ of length $nd$ from approximately $δδ_r nd$ erasures in time $n \cdot \mathrm{poly}(d2^r / δ）$，其中$δ$和$δ_r$是相对距离，$ r $'TH的广义相对距离分别为$ C_0 $。据我们所知，这是第一个线性时间算法，它可以从其（设计）距离（设计）大约$δ^2 nd $的擦除范围中列出删除。 为了获得我们的结果，我们表明一种类似于（Hemenway和Wootter，Information and Computation，2018）的方法可用于获得这种擦除列表编码算法，其运行时间对$ r $ and $δ$的运行时间的依赖性较差；然后，我们展示如何提高运行时间对这些参数的依赖性。
We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an inner code $C_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 $C = C(G, C_0)$ of length $nd$ from approximately $δδ_r nd$ erasures in time $n \cdot \mathrm{poly}(d2^r / δ)$, where $δ$ and $δ_r$ are the relative distance and the $r$'th generalized relative distance of $C_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 $δ^2 nd$. To obtain our results, we show that an approach similar to that of (Hemenway and 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 $δ$; then we show how to improve the dependence of the running time on these parameters.
