CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20190826-143512243

[img] PDF - Accepted Version
See Usage Policy.

293Kb
[img] PDF - Submitted Version
See Usage Policy.

240Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190826-143512243

Abstract

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
https://doi.org/10.1109/ISIT.2019.8849750DOIArticle
https://arxiv.org/abs/1910.12247arXivDiscussion Paper
https://resolver.caltech.edu/CaltechAUTHORS:20200409-105733198Related ItemTechnical Report
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
NSFCCF-1816965
NSFCCF-1717884
Record Number:CaltechAUTHORS:20190826-143512243
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190826-143512243
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
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:26 Aug 2019 21:39
Last Modified:09 Apr 2020 18:05

Repository Staff Only: item control page