Logarithmically larger deletion codes of all distances

2022/09/23 by Noga Alon, Gabriela Bourla, Alon, Noga +7 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.2209.11882

openalex publication_date 2022/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The deletion distance between two binary words u,v ∈ \0,1\ⁿ is the smallest k such that u and v share a common subsequence of length n-k. A set C of binary words of length n is called a k-deletion code if every pair of distinct words in C has deletion distance greater than k. In 1965, Levenshtein initiated the study of deletion codes by showing that, for k≥ 1 fixed and n going to infinity, a k-deletion code C⊆ \0,1\ⁿ of maximum size satisfies Ω_k(2ⁿ/n^2k) ≤ |C| ≤ O_k( 2ⁿ/n^k). We make the first asymptotic improvement to these bounds by showing that there exist k-deletion codes with size at least Ω_k(2ⁿ log n/n^2k). Our proof is inspired by Jiang and Vardy's improvement to the classical Gilbert--Varshamov bounds. We also establish several related results on the number of longest common subsequences and shortest common supersequences of a pair of words with given length and deletion distance.

Cited by

• Improved Constructions of Linear Codes for Insertions and Deletions
• Reconstruction Codes for Deletions and Insertions: Connection, Distinction, and Construction

Related

• Non-asymptotic Upper Bounds for Deletion Correcting Codes
• Perfect Multi Deletion Codes Achieve the Asymptotic Optimality of Code Size
• Explicit two-deletion codes with redundancy matching the existential\n bound
• Optimal k-Deletion Correcting Codes
• Optimal Codes Correcting a Burst of Deletions of Variable Length