Skip to content
Preprint

Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes

Oct 2026 · 0 citations · 27 references
Computer Science Mathematics

TL;DR

A new localization method is developed and used to construct a first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters.

Abstract

A $k$-substring edit in a sequence first deletes a substring of length at most $k$, and then inserts a sequence of length at most $k$ at the same position. A code that can correct a $k$-substring edit is called a $k$-substring edit code. In this paper, we develop a new localization method and use it to construct a $q$-ary $k$-substring edit correcting code with $\log n+8\log\log n+o(\log\log n)$ bits of redundancy for any fixed $q\ge2$ and $k\ge1$, where $n$ is the code length. For the binary alphabet, this improves upon the redundancy $\log n+16k\log\log n+o(\log\log n)$ obtained by Li \emph{et al}. When the deleted substring and the inserted sequence have different lengths, we further construct codes with redundancy $\log n+O_{q,k}(1)$, which is optimal up to an additive constant. As corollaries, for all fixed $q\ge2$ and $1\le t\le T$, we obtain $q$-ary $(\le t)$-burst-deletion correcting codes and $(t,T)$-localized deletion correcting codes with redundancies $\log n+O_{q,t}(1)$ and $\log n+O_{q,T}(1)$, respectively. To the best of our knowledge, these are the first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters. For $(\le t)$-burst-deletion correction with $t\ge2$, such redundancy had previously been achieved only for $q=t=2$ by Levenshtein in 1967.

View source

Similar papers

Sep 2026

Lower Bounds for all List-Decodable Deletion Codes

A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover the codeword. In this paper, we consider $t$-list decodable deletion codes, where after $k$ bits of a codeword are deleted, we can identify a...

Andrew D. Lin · 0 citations
Sep 2026

Polynomially larger deletion codes by linear hashing of substring counts

The result provides an edit-distance analogue of Varshamov's 1957 bound in the Hamming metric, both in the leading redundancy coefficient and in the role of linear independence in the proof.

Eyal En Gad · 4 citations · ⚡1
Preprint Oct 2026

Nonlinear fixed-distance codes via real lifts of moment configurations

Let $A_q(n,d)$ denote the largest size of a code of length $n$ and minimum Hamming distance $d$ over an alphabet of $q$ symbols. For fixed $q\ge2$ and $d\ge4$ we construct codes with redundancy $n-\log_q A_q(n,d)\le(d-3)\log_q n+O(\sqrt{\log n})$ for all large $n$. No algebraic structure is imposed on the alphabet, and...

S. Yekhanin · 1 citation
Preprint Nov 2026

Concatenation Locality under Successive Adjacent Transpositions

It is proved that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.

Adelin Ataba, Aryeh Lev Zabokritskiy · 0 citations
Sep 2026

Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets

We construct systematic $q$-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length $n\ge2$, our first construction has length $n+3$ over an alphabet of size $q=2^s<2^{32}n^7$ for some integer $s$, with polynomial-time encoding and decoding. A cardina...

V. Grishin, Aryeh Lev Zabokritskiy · 0 citations
Preprint Sep 2026

Exponentially Larger Deletion-Correcting Codes and Constant-List-Decodable Insertion-Deletion Codes

We establish improved asymptotic rate bounds for adversarial insertion--deletion codes. For binary unique-deletion correction in the linear-deletion regime, we strictly improve Levenshtein's classical lower-bound expression. At deletion fraction $\delta=0.1$, our achievable rate increases from $0.162009$ to $0.194890$,...

Han Mao Kiah, Heng-Jia Wei, Rui-Xiao Zeng · 2 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.