A Caltech Library Service

Optimal k-Deletion Correcting Codes

Sima, Jin and Bruck, Jehoshua (2019) Optimal k-Deletion Correcting Codes. Parallel and Distributed Systems Group Technical Reports, etr146. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Levenshtein introduced the problem of constructing k-deletion correcting codes in 1966, proved that the optimal redundancy of those codes is O(k log 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 8k log n+ o(log n) and encoding/decoding algorithms of complexity O(n^(2k+1)) for constant k.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription ItemConference Paper
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:This work was presented in part at the IEEE International Symposium on Information Theory, Paris, France, July 2019.
Group:Parallel and Distributed Systems Group
Series Name:Parallel and Distributed Systems Group Technical Reports
Issue or Number:etr146
Record Number:CaltechAUTHORS:20200409-105733198
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:102433
Deposited By: George Porter
Deposited On:09 Apr 2020 18:09
Last Modified:09 Apr 2020 18:09

Repository Staff Only: item control page