论文标题
针对对抗性插入和删除的线性代码的明确有效构造
Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions
论文作者
论文摘要
在这项工作中，我们研究了针对对抗插入 - 脱落（INSDEL）错误的线性误差校正代码，这个主题最近引起了很多关注。我们在$ \ mathbb {f} _q $上构造线性代码，对于$ q = \ text {poly}（1/\ varepsilon）$，可以有效地从$δ$ insdel错误的$δ$分数中解释，并具有速率$ $（1-4Δ）/8- \ varepsilon $。我们还表明，通过在$ \ mathbb {f} _ {q^2} $上允许代码在$ \ mathbb {f} _q $上线性，我们可以将速率提高到$（1-Δ）/4- \ varepsilon $，而不是牺牲效率。使用后一个结果，我们在$ \ mathbb {f} _2 $上构造了完全线性代码，该代码可以有效地校正最高$Δ<1/54 $删除的含量，并具有$ r =（1-54 \cdotΔ）/1216 $。 Cheng，Guruswami，Haeupler和Li [CGHL21]构建了代码，其速率（极小）速率远离零，可以校正高达$Δ<1/400 $的INSDEL错误分数。他们还提出了构建线性代码的问题，该线性代码接近在小场上（在[CGHL21]中证明）的半灵子界。因此，我们的结果显着改善了它们的构建，并更加接近界限。
In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over $\mathbb{F}_q$, for $q=\text{poly}(1/\varepsilon)$, that can efficiently decode from a $δ$ fraction of insdel errors and have rate $(1-4δ)/8-\varepsilon$. We also show that by allowing codes over $\mathbb{F}_{q^2}$ that are linear over $\mathbb{F}_q$, we can improve the rate to $(1-δ)/4-\varepsilon$ while not sacrificing efficiency. Using this latter result, we construct fully linear codes over $\mathbb{F}_2$ that can efficiently correct up to $δ< 1/54$ fraction of deletions and have rate $R = (1-54\cdot δ)/1216$. Cheng, Guruswami, Haeupler, and Li [CGHL21] constructed codes with (extremely small) rates bounded away from zero that can correct up to a $δ< 1/400$ fraction of insdel errors. They also posed the problem of constructing linear codes that get close to the half-Singleton bound (proved in [CGHL21]) over small fields. Thus, our results significantly improve their construction and get much closer to the bound.
