CS Paper Radar

Concatenation Locality under Successive Adjacent Transpositions

Adelin Ataba, Aryeh Lev Zabokritskiy

cs.IT ·submitted 2026-11-01 20:38 UTC · v1
theory

Abstract

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$.

Comment
32 pages

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.70
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.69
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

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

cs.IT ·2026-09-29 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.68
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

On Optimal Encodings and Systematicity in Function-Correcting Codes

cs.IT ·2026-10-06 ·Charul Rajput, Kanchana Lokshmii Jagatti, B. Sundar Rajan
theory similarity 0.68
Abstract

Function-correcting codes (FCCs) protect the value of a function $f$ of the message against $t$ errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of $2t$ on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs $2t$. For a linear function $f$ and a fixed linear code $C$, let $d_f$ denote the minimum distance between codewords of messages with different function values. Different generator matrices of $C$ assign different codewords to the messages and can give different values of $d_f$. We study which generator matrix of $C$ gives the largest $d_f$. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of $C$. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of $C$ alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic $(f,t)$-FCC of length $n$ exists if and only if a condition depending on $f$ only through the size of its smaller preimage holds. For $t=1$, redundancy $1$ is sufficient for every nonconstant two-valued function on $\mathbb{F}_2^k$ with $k\ge 10$. For general $t$, redundancy $1$ suffices for all two-valued functions once $k$ is large enough, and for each $s<2t$ we give an upper bound on the threshold in $k$ beyond which redundancy $s$ suffices.

0.15

Polynomially larger deletion codes by linear hashing of substring counts

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

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

cs.IT ·2026-10-05 ·Zuo Ye, Gennian Ge
similarity 0.65
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

New lower bounds for constant-weight codes via seeded bit-swap tabu search

cs.IT math.CO ·2026-08-14 ·William Echols
similarity 0.65
Abstract

A binary constant-weight code is a set of binary words of length $n$ such that each word has exactly weight $w$ and is at least Hamming distance $d$ from every other word in the set. $A(n,d,w)$ denotes the maximum size of a binary constant-weight code with parameters $(n,d,w)$. Using seeded initialization with bit-swap tabu search, we found 124 new constructions that improve existing lower bounds for $A(n,d,w)$. As a corollary of stronger bounds on $A(n,8,8)$ for $n \in \{ 32,33,34,37 \}$, we also improve lower bounds on kissing numbers $τ_{32}$, $τ_{33}$, $τ_{34}$, and $τ_{37}$.

0.40

Target-Dependent Local Verification: Information--Proof-Length Tradeoffs

cs.CC ·2026-08-22 ·Hongmin Li
theory similarity 0.65
Abstract · 15 pages. Submitted to computational complexity

We study fixed-layout local verification with target-dependent local tests. Let $M$ be a random variable on $\{0,1\}^K$, and let $S$ record the test selected at each coordinate. For each $s\in\operatorname{supp}(S)$, let $F_s$ be the corresponding target fiber and set $D_{\mathrm{fib}}=\max_s\operatorname{VCdim}(F_s)$. We prove $H(M\mid S)\le \log_2\!\left(\sum_{j=0}^{D_{\mathrm{fib}}}\binom Kj\right)$. A fiber that shatters $d$ coordinates yields a weak relaxed locally decodable code with message length $d$ and block length $d+P$ over the original proof alphabet. For a uniform $K$-bit target and fixed proof alphabet, $Q$, and $σ$, the Goldberg--Gur--Saraogi lower bound implies that $I(M;S)\leγK$, for fixed $γ<1$, forces $P=Ω\!\left(K^{1+1/a}/(\log K)^{2+2/a}\right)$, where $a=\lceil Q/σ\rceil$. If $P\le K(\log K)^c$, then $I(M;S)\ge K-O\!\left(K^{a/(a+1)}(\log K)^{3+ac/(a+1)}\right)=K-o(K)$. Any discrete verifier state $T$ determining $S$ satisfies the same information lower bound. Bounded-randomness adaptive branches can be simulated nonadaptively by exposing their decision trees. A branch using at most $r$ random bits and $q$ adaptive proof queries yields a decoder with perfect completeness and at most $1+2^{r+1}\sum_{j<q}A^j$ queries. Under $I(M;S)\leγK$, near-linear proof length requires this quantity to be $Ω(\log K/\log\log K)$; the binary one-query case gives $P=2^{Ω(K)}$. Applied to a global list-sound dPCP interface of Gur--Minzer--Weissenberg--Zheng, our bound shows that a fixed target-independent menu of $L$ test profiles must satisfy $\log_2L\ge K-o(K)$. Proof-dependent lists and additional target-dependent selection data must be included in the measured state.

0.32