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

We give a complete answer to the following basic question: "What is themaximal fraction of deletions or insertions tolerable by $q$-ary list-decodablecodes with non-vanishing information rate?"  This question has been open even for binary codes, including the restrictionto the binary insertion-only setting, where the best-known result was that a$\gamma\leq 0.707$ fraction of insertions is tolerable by some binary codefamily.  For any desired $\epsilon > 0$, we construct a family of binary codes ofpositive rate which can be efficiently list-decoded from any combination of$\gamma$ fraction of insertions and $\delta$ fraction of deletions as long as $\gamma+2\delta\leq 1-\epsilon$. On the other hand, for any $\gamma,\delta$ with$\gamma+2\delta=1$ list-decoding is impossible. Our result thus preciselycharacterizes the feasibility region of binary list-decodable codes forinsertions and deletions.  We further generalize our result to codes over any finite alphabet of size$q$. Surprisingly, our work reveals that the feasibility region for $q>2$ isnot the natural generalization of the binary bound above. We provide tightupper and lower bounds that precisely pin down the feasibility region, whichturns out to have a $(q-1)$-piece-wise linear boundary whose $q$ corner-pointslie on a quadratic curve.  The main technical work in our results is proving the existence of codefamilies of sufficiently large size with good list-decoding properties for anycombination of $\delta,\gamma$ within the claimed feasibility region. Weachieve this via an intricate analysis of codes introduced by [Bukh, Ma; SIAMJ. Discrete Math; 2014]. Finally, we give a simple yet powerful concatenationscheme for list-decodable insertion-deletion codes which transforms any such(non-efficient) code family (with vanishing information rate) into anefficiently decodable code family with constant rate.

Optimally Resilient Codes for List-Decoding from Insertions and Deletions