CS Paper Radar

Lower Bounds for all List-Decodable Deletion Codes

Andrew D. Lin

cs.IT cs.DMmath.CO ·submitted 2026-09-22 16:18 UTC · v1
theory

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.

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

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

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

Quadratic reset bounds for finite maximal prefix codes

cs.FL ·2026-11-03 ·Samrath Singh Chadha
theory similarity 0.69
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

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.69
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences

cs.IT math.CO ·2026-10-26 ·Nader H. Bshouty
theory similarity 0.69
Abstract

Let $d_{K_{s,t}}(n)$ be the largest fraction of all graphs on $[n]$ in a family containing no two distinct members whose symmetric difference is a copy of $K_{s,t}$. We determine this maximum density for every fixed pair of positive integers $s,t$. If both part sizes are odd, it is known that the density is exactly $1/2$. Otherwise, let $2h$ be the largest even part size. We prove $$ d_{K_{s,t}}(n)=Θ_{s,t}(n^{-h}). $$ For $h>1$, this improves the general $O_{s,t}(1/n)$ upper bound obtained from Alon's two-copy gluing theorem~\cite{Alon2024}. The sharp bounds for even stars were already proved by Alon and are recovered as special cases. The upper bound uses the Frankl--Füredi forbidden-intersection theorem. For the lower bound, we construct binary linear codes using BCH codes. When exactly one part size is even, we assign to each edge the sum of the binary vectors assigned to its endpoints. When both part sizes are even, we identify these vectors with elements of a finite field and assign to each edge the product of its endpoint elements. In both cases, every copy of $K_{s,t}$ has a nonzero syndrome.

0.27

Improving the Trifference Lower Bound via Non-Perfect Hashing

cs.IT ·2026-11-08 ·Chen Yuan, Ruiqi Zhu
theory similarity 0.68
Abstract · 18 pages

We strictly improve the Körner-Marton lower bound $\frac14\log \frac{9}{5}$ on the asymptotic rate of trifferent codes. We obtain this improvement by constructing non-perfect $(9,3)$-hash codes with rate above $\log(9/5)$ and then applying the Tetra-code construction, which gives $R_3\ge\frac14R_{9,3}$. More generally, for every $q\ge4$, we prove $R_{q,3}>B_{q,3}+\frac1{250000}$. We also extend the method to $(p,2,3)$-list recovery. For every $q\ge4$ and $0\le p<\frac{q-2}{12(q-1)}$, we prove $R_q^{\mathrm{LR}}(p)>B_q^{\mathrm{LR}}(p)$. Here $B_{q,3}$ and $B_q^{\mathrm{LR}}(p)$ denote the respective probabilistic lower bounds. For every fixed $0\le p<1/18$, the rate improvement is bounded below by a positive constant independent of $q\ge4$. For every fixed $0\le p<1/12$, we also obtain a positive rate improvement independent of $q$ for all sufficiently large $q$.

0.21

Deterministic Constructions of Reed-Solomon Codes Beyond the Johnson Bound

cs.CC ·2026-10-22 ·Abhranil Chatterjee, Sumanta Ghosh, Zeyu Guo, Rohit Gurjar, Roshan Raj +1 more
similarity 0.68
Abstract

We give a deterministic quasipolynomial-time construction of Reed-Solomon codes that are list-decodable beyond the Johnson radius. Specifically, for every $ε\in(0,1]$ and all sufficiently large $n$, we construct an $[n,k]$ Reed-Solomon code of rate $R=Ω(ε/(1+\log(1/ε)))$ over a field of size $(nk)^{quasi-poly(nk)}$ that is $(1-ε,O(1/ε))$ list-decodable. The construction runs in quasi-poly(nk) time. We also give a deterministic construction of $[n,k]$-MDS$(3)$ Reed-Solomon codes for all integers $1\leq k<n$, with the same asymptotic bounds on field size and construction time. In the constant-rate regime, our field-size bound substantially improves the bound of $O(n^{k^{2k}})$ achieved by Roth's construction (Roth, IEEE TIT 2022). Our constructions exploit a connection to polynomial identity testing for read-once determinants, together with the quasipolynomial isolating-weight construction of Gurjar and Thierauf for linear matroid intersection (Gurjar and Thierauf, STOC 2017 and Computational Complexity 2020).

0.20