A Caltech Library Service

Optimal k​-Deletion Correcting Codes

Sima, Jin and Bruck, Jehoshua (2019) Optimal k​-Deletion Correcting Codes. In: 2019 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 847-851. ISBN 978-1-5386-9291-2.

[img] PDF - Accepted Version
See Usage Policy.

[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:Book Section
Related URLs:
URLURL TypeDescription Paper ItemTechnical Report
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2019 IEEE. The work was supported in part by NSF grants CCF-1816965 and CCF-1717884.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20190826-143512243
Persistent URL:
Official Citation:J. Sima and J. Bruck, "Optimal k-Deletion Correcting Codes," 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France, 2019, pp. 847-851. doi: 10.1109/ISIT.2019.8849750
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98251
Deposited By: George Porter
Deposited On:26 Aug 2019 21:39
Last Modified:16 Nov 2021 17:37

Repository Staff Only: item control page