English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work, we study linear error-correcting codes against adversarialinsertion-deletion (insdel) errors, a topic that has recently gained a lot ofattention. We construct linear codes over $\mathbb{F}_q$, for$q=\text{poly}(1/\varepsilon)$, that can efficiently decode from a $\delta$fraction of insdel errors and have rate $(1-4\delta)/8-\varepsilon$. We alsoshow that by allowing codes over $\mathbb{F}_{q^2}$ that are linear over$\mathbb{F}_q$, we can improve the rate to $(1-\delta)/4-\varepsilon$ while notsacrificing efficiency. Using this latter result, we construct fully linearcodes over $\mathbb{F}_2$ that can efficiently correct up to $\delta < 1/54$fraction of deletions and have rate $R = (1-54\cdot \delta)/1216$. Cheng,Guruswami, Haeupler, and Li [CGHL21] constructed codes with (extremely small)rates bounded away from zero that can correct up to a $\delta < 1/400$ fractionof insdel errors. They also posed the problem of constructing linear codes thatget close to the half-Singleton bound (proved in [CGHL21]) over small fields.Thus, our results significantly improve their construction and get much closerto the bound.

Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions