Optimal k-Deletion Correcting Codes

2019/10/27 by Jin Sima, Sima, Jin, Jehoshua Bruck +1 · 9 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.1910.12247

openalex publication_date 2019/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Levenshtein introduced the problem of constructing k-deletion correcting codes in 1966, proved that the optimal redundancy of those codes is O(klog N), and proposed an optimal redundancy single-deletion correcting code (using the so-called VT construction). However, the problem of constructing optimal redundancy k-deletion correcting codes remained open. Our key contribution is a solution to this longstanding open problem. We present a k-deletion correcting code that has redundancy 8klog n +o(log n) and encoding/decoding algorithms of complexity O(n^2k+1) for constant k.

Cited by

• Constructing Low-Redundancy Codes via Distributed Graph Coloring
• Block Length Gain for Nanopore Channels
• Improved Constructions of Linear Codes for Insertions and Deletions
• Efficient Decoding of Insertion and Deletion Errors for Helberg Codes
• On the Maximum Size of Codes Under the Damerau-Levenshtein Metric
• Correcting Bursty/Localized Deletions: A New Error-Position-Estimation Code
• Correcting Errors Through Partitioning and Burst-Deletion Correction
• Criss-Cross Deletion Correcting Codes: Optimal Constructions with Efficient Decoders
• Oblivious Deletion Codes

Related

• Optimal Codes Correcting a Burst of Deletions of Variable Length
• Optimal codes in deletion and insertion metric
• Systematic Single-Deletion Multiple-Substitution Correcting Codes
• Construction of optimal codes in deletion and insertion metric
• An Improvement to Levenshtein's Upper Bound on the Cardinality of\n Deletion Correcting Codes