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) https://resolver.caltech.edu/CaltechAUTHORS:20200409-105733198
![]() |
PDF
- Submitted Version
See Usage Policy. 344kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200409-105733198
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: | Report or Paper (Technical Report) | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
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: | https://resolver.caltech.edu/CaltechAUTHORS:20200409-105733198 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 102433 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | George Porter | ||||||
Deposited On: | 09 Apr 2020 18:09 | ||||||
Last Modified: | 09 Apr 2020 18:09 |
Repository Staff Only: item control page