CS Paper Radar

Coding for Multiple Reverse-Complement and Palindromic Duplications

Aryeh Lev Zabokritskiy

cs.IT ·submitted 2026-09-01 06:20 UTC · v4
theory

Abstract

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.

Comment
33 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Concatenation Locality under Successive Adjacent Transpositions

cs.IT ·2026-11-01 ·Adelin Ataba, Aryeh Lev Zabokritskiy
theory similarity 0.70
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

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

Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes

cs.IT ·2026-10-28 ·Ruho Kondo, Yota Maeda
similarity 0.64
Abstract · 13 pages, 5 figures,

Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.

0.23

On the Average List Size of VT Codes under Two Insertions or Two Deletions

cs.IT ·2026-10-11 ·Anisha Banerjee, Roni Con, Antonia Wachter-Zeh, Eitan Yaakobi
theory similarity 0.64
Abstract · Submitted to ITW 2027

Levenshtein's classical theorem shows that any code that can uniquely decode from \(t\) deletions can also uniquely decode from \(t\) insertions. This symmetry, however, does not generally hold in the list-decoding regime. Several prior results on the capacity and radii of list-decoding from insertions and deletions suggest that insertions are easier to handle than deletions. In an effort to better understand this asymmetry between insertions and deletions under list-decoding, we study an analogous version of McEliece's \emph{average list size problem}. More precisely, given a binary code \(\mathcal{C}\) of length \(n\) that uniquely corrects \(t'\) insertions (or deletions), we are interested in the average number of codewords returned by a \(t\)-insertion (or deletion) list decoder, where \(t' < t\). Focusing on the case of \(t'=1\) and \(t=2\), we find that under two insertions, this quantity is at most \((n+12)/4\) for any VT code of length \(n\), whereas under two deletions it is at least \(n/2 - 10\) when averaged over all length-\(n\) VT codes. The nearly factor-of-two gap between these upper and lower bounds serves to confirm the relative ease of list-decoding of insertions compared to deletions from an average-case perspective.

0.22

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

Quadratic reset bounds for finite maximal prefix codes

cs.FL ·2026-11-03 ·Samrath Singh Chadha
theory similarity 0.64
Abstract

Let $C$ be a finite maximal prefix code of maximum codeword length $k\ge2$. We prove that, whenever the literal decoder of $C$ is synchronizing, it has a reset word of length at most $(k-1)(4k-5)$. The bound is independent of the alphabet and the number of decoder states. Its main ingredient is a short-detection theorem: a linear observation of the decoder, with terminal weight constant on states of depth $k-1$, is either identically zero or nonzero on a word of length at most $2k-3$. The proof uses a first-return decomposition in noncommuting variables and cancellation of a highest-degree coefficient. For codes whose codeword lengths are $k-1$ and $k$, we prove the sharper bound $2(k-1)^2-1$ and characterize equality. The binary code with the single short word $a^{k-1}$ attains this bound for every $k\ge2$; an age representation and a potential on circular arcs give the matching lower bound. Both upper bounds yield polynomial-time constructions in the explicit code size. The mathematical results and the algorithms are formalized in Lean, with polynomial work bounds in a specified binary cost model.

0.12

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.64
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.38

On Sequence Reconstruction Problem for q-ary Deletion Channels

cs.IT ·2026-09-15 ·Xiang Wang, Han Li, Fang-Wei Fu
theory similarity 0.64
Abstract

The sequence reconstruction problem for $q$-ary deletion channels, introduced by Levenshtein in 2001, concerns the minimum number of channels required to uniquely recover a transmitted sequence when each channel introduces exactly $t$ deletions. Combinatorially, it is equivalent to determining $N_q(n,d,t)$, the maximum intersection size of two $t$-deletion balls with centers at Levenshtein distance at least $d$, for $q$-ary sequences of length $n$ over the alphabet \(Σ_q=\{0,1,\dots,q-1\}\). Levenshtein solved the uncoded case $N_q(n,1,t)$ for all $n\ge t$; subsequently, Gabrys and Yaakobi determined $N_2(n,2,t)$, and Wang et al. extended the result to $N_3(n,2,t)$. In this paper, we study the problem for \(q\)-ary sequences under minimum Levenshtein distance \(d=2\) with channels that introduce exactly \(t\) deletions. We determine the exact value of \(N_q(n,2,t)\) for all \(t\ge 2, q\geq 4\), and for sufficiently large \(n\), and construct explicit pairs of sequences attaining the maximum intersection. Furthermore, for each $q\ge3$, we characterize all extremal sequence pairs. In particular, if the intersection size matches the first two terms of \(N_q(n,2,t)\), then the two center sequences must contain, at the same positions, length-5 blocks of the forms \((a,b,c,a,b)\) and \((b,a,c,b,a)\) for some distinct \(a,b,c\inΣ_q\); for \(t\ge q+2\), the exact maximum \(N_q(n,2,t)\) is attained precisely by \(2q!\) unordered pairs of sequences with a specific block structure. Asymptotically, we prove that for \(q\ge 4\) and \(t\ge 2\), \[ N_q(n,2,t)=\frac{6}{(t-2)!}n^{t-2}-\frac{3t+13}{(t-3)!}n^{t-3}+\frac{3t^2+25t+64}{4(t-4)!}n^{t-4}+O(n^{t-5}). \] Moreover, \(N_q(n,2,t)\) and \(N_{q-1}(n,2,t)\) share their first \(q-1\) terms, and for \(t\ge q\) the coefficient of \(n^{t-q}\) in their difference is \(\frac{6t-6q+5}{(t-q)!}\).

0.23