CS Virtual Colloquium: Constructing Deletion/Insertion Correcting Codes with Order-wise Optimal Redundancy

 

Dr. Jin Sima, UIUC

10/25/2022 at 3:00pm

 

Join Zoom Meeting

https://purdue-edu.zoom.us/j/4631947792

 

Title: Constructing deletion/insertion correcting codes with order-wise optimal redundancy

Abstract: Constructing codes that correct deletion/insertion errors is one of the fundamental problems in information and coding theory that has applications in DNA storage, packet transmission, etc. Unlike erasure and substitution correcting codes, which are well understood with many classic results, correcting deletion/insertion errors is more elusive due to the loss of positional information. It was shown by Levenshtein, who introduced the problem of deletion/insertion correcting codes in the 1960s, that the optimal redundancy of length n codes correcting k deletions lies between k log ⁡n+o(log ⁡n) and 2 k log ⁡n+o(log⁡ n). Yet, for many years no explicit code constructions correcting k deletion/insertion errors with sublinear redundancy were known even for k=2, until a series of recent breakthroughs. In this talk, we focus on the regime when k is a constant with respect to n. We present length n codes correcting k deletions with 4 log⁡ n+o(log⁡ n) redundancy, which is at most four times the optimal redundancy. Our codes are systematic, which also find applications in file exchange. The encoding/decoding complexity is O(n^{2k+1}) which is polynomial with constant k.

Bio: Jin Sima is postdoc in the Department of Electrical and Computer Engineering at University of Illinois Urbana-Champaign. He received a B.Eng. and a M.Sc. in electronic engineering from Tsinghua University, China, in 2013 and 2016 respectively, and a Ph.D in electrical engineering from California Institute of Technology (Caltech) in 2022.

His research interests include information and coding theory, with its applications in data storage systems. He is a recipient of the 2019 IEEE Jack Keil Wolf ISIT Student Paper Award.