CS Paper Radar

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

Quan D. Bui, Shuche Wang, Manabu Hagiwara, Van Khu Vu

cs.IT cs.DM ·submitted 2026-10-11 14:01 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Coding for Multiple Reverse-Complement and Palindromic Duplications

cs.IT ·2026-09-01 ·Aryeh Lev Zabokritskiy
theory similarity 0.64
Abstract · 33 pages

Reverse-complement (RC) and palindromic (PAL) duplications insert a reversed copy of a length-$k$ block immediately after the block; an RC duplication also applies a fixed involutive complement to the inserted symbols. We study $q$-ary codes correcting $t$ such operations applied in sequence, where later operations may copy inserted symbols. For fixed $q\geq2$ and $k,t\geq1$, we prove that every length-$n$ code $C$ for either channel has redundancy $n-\log_q|C|\geq t\log_q n-O_{q,k,t}(1)$; for fixed $q,k$ and $1\leq t=t(n)=o(n)$ the lower bound is $t\log_q(n/t)-O_{q,k}(t)$. For fixed $k$, known codes for one length-$k$ insertion burst attain redundancy $\log_q n+O_{q,k}(1)$ for a single duplication of either type. For every even $k$ and any involutive complement, we show that the two channels are equivalent for every number of errors: the bijection complementing every other coordinate turns each RC duplication into a PAL duplication. This bijection therefore converts any $t$-error-correcting RC code into a PAL code of the same size, and conversely, with linear-time transfer of encoders and decoders. For every even $k$, we also determine the maximum number of descendants of one word under exactly two errors; by the bijection, it is the same for both channels. For fixed even $k$, a direct count using this maximum proves the existence of two-error-correcting PAL and RC codes with redundancy at most $4\log_q n+O_{q,k}(1)$. A known existence bound for two deletion bursts transfers to insertions with the same leading term as ours and a larger additive constant. For two errors, the converse gives $2\log_q n-O_{q,k}(1)$, a factor of two below these existence bounds.

0.31

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

cs.IT ·2026-11-02 ·Ryan Gabrys, Shubhransh Singhvi, Eitan Yaakobi
similarity 0.63
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.

0.41

One Burst of t-Deletion and One Burst of t-Substitution Error-Correcting Codes

cs.IT ·2026-08-25 ·Yajuan Liu, Han Cai, Tolga M. Duman
published similarity 0.63
Abstract

Synchronization errors, including insertions, deletions, and substitutions, may occur in bursts in communication systems such as DNA data storage, file synchronization, and magnetic recording. In this paper, we study an error model con?sisting of one burst of t-deletions and one burst of t-substitutions. By reformulating the original sequence into a matrix form, we propose an explicit construction of error-correcting codes capable of correcting one burst of t-deletions and one burst of t-substitutions with O(log n) redundancy.

0.57

Order-Optimal Systematic Permutation Codes for Correcting t Deletions

cs.IT ·2026-09-29 ·Bolin Wu, Quan D. Bui, Kai Niu, Van Khu Vu, Shuche Wang
similarity 0.62
Abstract

This paper investigates the construction of full-systematic permutation codes capable of correcting multiple deletions under two complementary models, namely symbol-invariant deletions (SIDs), where surviving symbol values are preserved, and permutation-invariant deletions (PIDs), where the surviving sequence is standardized to a permutation. For any fixed integer $t \ge 1$ and all sufficiently large message lengths $n$, our proposed encoders map any message permutation of length $n$ to a codeword by inserting distinct redundancy symbols while strictly preserving the sequence order of the original message symbols. The proposed constructions correct up to $t$ deletions using $7t-1$ redundancy markers for PIDs and $4t$ redundancy markers for SIDs, achieving redundancies of $(7t-1)\log n + O_t(1)$ bits and $4t\log n + O_t(1)$ bits, respectively. Both code families are uniformly constructible, encodable, and decodable in $n^{O(t)}$ time. The underlying framework stores an inner deletion-correcting syndrome in the relative positions of redundancy markers via an algebraic outer code based on integer moments and residual graph coloring. We further extend this framework to fixed-composition and strictly $λ$-regular multipermutations, proving that the PID and SID channels coincide whenever the common multiplicity satisfies $λ> t$.

0.39

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.62
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.61
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

Minimum Synthesis Time for Single-Deletion Correcting Codes of Prescribed Size

cs.IT ·2026-11-10 ·Yuling Li, Wenjun Yu, Gennian Ge
similarity 0.60
Abstract

DNA is a promising medium for data storage, but the high cost of DNA synthesis remains a major obstacle to its widespread deployment. In the reference-based synthesis model, synthesis time is measured by the length of the reference sequence. Previous studies have analyzed code sizes under synthesis-time constraints and constructed cost-constrained codes, including codes that correct deletions. In this paper, we study the minimum synthesis time for codes of prescribed size, considering both unrestricted codes and single-deletion correcting codes. We establish finite-length lower bounds valid for arbitrary reference sequences and upper bounds using existing $q$-ary differential VT codes. For fixed $q\geq3$, $A>0$, and $R\in(0,1)$, we determine the minimum synthesis time up to an $O(1)$ term when the code size is $M_n=\lfloor Aq^{Rn}\rfloor$. The corresponding redundancy is $(1-R)n\log_2q-\log_2A+o(1)$ bits. In particular, for these code sizes, the minimum synthesis time for single-deletion correcting codes exceeds that for unrestricted codes by a term proportional to $\ln n$, and we determine its coefficient. We also derive upper and lower bounds for code sizes $\lfloor q^n/(nq^{s_n})\rfloor$, where $s_n\to\infty$ and $s_n=o(n)$. These sizes correspond to redundancy $\log_2 n+s_n\log_2q+o(1)$ bits. For code sizes $\lfloor q^n/(nq^c)\rfloor$ with fixed constant $c$, the redundancy is $\log_2 n+c\log_2q+o(1)$ bits. We give conditions under which single-deletion correcting codes exist or do not exist for all sufficiently large $n$, together with bounds on the minimum synthesis time. These results show how code size and the single-deletion correcting constraint affect synthesis time and provide theoretical guidance for the construction of cost-constrained codes.

0.24

Polynomially larger deletion codes by linear hashing of substring counts

cs.IT math.CO ·2026-09-16 ·Eyal En Gad
highly cited similarity 0.60
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