CS Paper Radar

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound

Ryan Gabrys, Shubhransh Singhvi, Eitan Yaakobi

cs.IT ·submitted 2026-11-02 22:08 UTC · v1

Abstract

We construct binary codes that attain the classical Gilbert-Varshamov redundancy guarantee for a fixed number of edit errors, with deterministic polynomial-time construction, encoding, and decoding. For every fixed integer $t\ge 1$ and all sufficiently large block lengths $n$, our codes correct any combination of at most $t$ insertions, deletions, and substitutions in total, with redundancy at most $2t\log_2 n+O_t(1)$. All algorithms run in polynomial time in $n$ for fixed $t$, and decoding recovers the original information message. This realizes the classical counting guarantee algorithmically without enumerating the exponentially large space of binary words.

Closest papers

Nearest neighbours by meaning across the whole index.

Polynomially larger deletion codes by linear hashing of substring counts

cs.IT math.CO ·2026-09-16 ·Eyal En Gad
highly cited similarity 0.71
Abstract · Extended to arbitrary fixed alphabets, mixed edits, and bounded substring edits; simplified proof using binary linear hashing

We reduce the leading redundancy coefficient for binary codes correcting any fixed number $t\ge2$ of deletions from $2t$ to $2t-1$. This is the first improvement to that coefficient since Levenshtein's 1965 bound. More generally, over every fixed alphabet of size $q\ge2$, codes of length $n$ correcting any combination of at most $t$ insertions, deletions and substitutions exist with redundancy $(2t-1)\log_q n+O_t(\log_q\log_q n)$. For two deletions, the upper-bound coefficient drops from $4$ to $3$, halving the gap to the lower-bound coefficient $2$. The leading coefficient $2t-1$ also holds for $t$ bounded substring edits, where both the removed and inserted strings have bounded length. The proof combines random binary linear hashing of substring counts with a two-colouring argument. A linear dependence among differences of substring-count vectors forces their local changes to overlap, and this overlap lowers the redundancy coefficient from $2t$ to $2t-1$. 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.

0.51

Concatenation Locality under Successive Adjacent Transpositions

cs.IT ·2026-11-01 ·Adelin Ataba, Aryeh Lev Zabokritskiy
theory similarity 0.69
Abstract · 32 pages

We study codes correcting up to $t\geq1$ successive adjacent transpositions, using block concatenation to support blockwise encoding and decoding. A fixed set $P$ of words of length $b$ over a $q$-symbol alphabet generates, for every $m$, the length-$mb$ code of all concatenations of $m$ words from $P$. For our explicit constructions, the prepared encoder and decoder depend only on the block parameters and are reused at every concatenation length. We first prove that correction at every concatenation length is certified by a single finite test at $2t+1$ blocks, and this test is tight over a $q$-symbol alphabet exactly when $\binom q2\geq2t$. For binary words and $b\geq2t+1$, we give an explicit construction with total redundancy at most $mt\log_2 b+O_t(m)$, matching the optimal per-block redundancy $t\log_2 b+O_t(1)$ among block sets correcting at every concatenation length. Among all binary $t$-correcting codes of length $mb$, the optimal total redundancy is $t\log_2(mb)+O_t(1)$. Using all concatenations of one block set makes our total redundancy grow linearly in $m$ and buys independent block encoding, with one encoder and decoder at every length. The construction encodes and decodes in time linear in $mb$ for fixed $b,t$, and recovers the $j$-th source block from the first $jb$ received symbols. We also prove that, whenever the length-$mb$ code corrects $t$ transpositions, the $j$-th source block is determined within $2tb$ received symbols beyond position $jb$, and that explicit binary block sets with rates tending to one as $b$ grows with $t$ fixed attain this bound in the worst case. Finally, we prove that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.

0.28

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

cs.IT ·2026-09-29 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.67
Abstract · 52 pages

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 cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size $O(n^4)$, leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size $q<(n+2)^4$. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for $n\ge2$.

0.12

A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors

cs.IT math.CO ·2026-10-16 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.66
Abstract

We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most $n - \frac{L}{L+1}k + 1$ insdel errors with fixed list size $L$, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size $q \geq 3$.

0.07

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

cs.IT ·2026-10-05 ·Zuo Ye, Gennian Ge
similarity 0.66
Abstract · 35 pages

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.

0.17

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

cs.IT ·2026-09-18 ·Han Mao Kiah, Hengjia Wei, Ruixiao Zeng
theory similarity 0.65
Abstract · 46 pages, 7 figures

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 $δ=0.1$, our achievable rate increases from $0.162009$ to $0.194890$, a relative gain of approximately $20.30\%$. For list decoding with any prescribed finite list size $L$, we obtain new achievable-rate bounds for binary deletion and insertion codes. Our approach combines the Lovász local lemma with refined counting of common subsequences and supersequences, using generating functions and run-restricted sampling. We also establish a combinatorial reduction that trades $L$ units of insertion budget for one unit of deletion budget without changing the code or increasing the list size. It transfers insertion lower bounds at $γ+Lδ$ and deletion upper bounds at $δ+γ/L$ to mixed errors. We also derive a run-counting Levenshtein-type list-decoding upper bound and a higher-order Elias-type upper bound. The latter recovers Yasunaga's asymptotic unique-decoding bound at $L=1$ and strictly improves the Haeupler--Shahrasbi--Sudan insertion upper bound for every fixed $L$ and $0<γ<q-1$. Numerical comparisons quantify the gains and the remaining gaps.

0.41

Lower Bounds for all List-Decodable Deletion Codes

cs.IT cs.DMmath.CO ·2026-09-22 ·Andrew D. Lin
theory similarity 0.64
Abstract

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 list of size at most $t$ such that the original codeword lies in the list. We prove a lower bound of $Ω_k(2^n t\log^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$. Our bound holds for all $t\leq n^k$, showing that $t=Ω(\log n)-$list decodable deletion codes have optimal size $Θ_k(2^n t/n^k)$, asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.

0.06

Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound

cs.IT cs.DM ·2026-10-11 ·Quan D. Bui, Shuche Wang, Manabu Hagiwara, Van Khu Vu
similarity 0.63
Abstract

Correcting synchronization errors is one of the oldest problems in coding theory. In the mid-1960s, Levenshtein, and independently Ullman, showed that a single deletion can be corrected with $\log n+O(1)$ bits of redundancy, which is asymptotically optimal. For any fixed $t$, a Gilbert--Varshamov (GV) type argument shows that codes correcting $t$ deletions exist with redundancy $2t\log n+O_t(1)$. Achieving this classical GV-type bound explicitly has proved remarkably difficult. Explicit codes with redundancy $O_t(\log n)$ were first obtained by Brakensiek, Guruswami, and Zbarsky in 2016, half a century after Levenshtein, and Guruswami and Håstad matched the GV-type bound for two deletions only in 2021. For every fixed $t\ge 3$, the best explicit constructions still require roughly twice the GV-type redundancy: $(4t-1)\log n+o(\log n)$ for $t$ deletions and $4t\log n+O_t(\log\log n)$ for $t$ edits (insertions, deletions, and substitutions). We close this factor-of-two gap for every fixed $t$, even in the Damerau--Levenshtein model, which also allows adjacent transpositions. We construct explicit binary codes with deterministic polynomial-time encoding and decoding that correct any combination of at most $t$ such errors using $2t\log n+2t\log\log n+O_t(\log\log\log n)$ bits of redundancy. A single construction thus achieves the leading term of the classical GV-type bound simultaneously for deletions, edits, and Damerau--Levenshtein errors, extending the Guruswami--Håstad result from two deletions to every fixed $t$ and to substantially richer error models.

0.17