All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-S3-T4.3
Paper Title Correcting Two Deletions with More Reads
Authors Johan Chrisnata, NANYANG TECHNOLOGICAL UNIVERSITY, Singapore; Han Mao Kiah, Nanyang Technological University, Singapore
Session D6-S3-T4: Multiple Insertion/Deletion-Correcting Codes
Chaired Session: Monday, 19 July, 22:40 - 23:00
Engagement Session: Monday, 19 July, 23:00 - 23:20
Abstract A two-deletion correcting code of length n is defined to be a set of binary words such that a codeword can be uniquely identified from any one of its length-(n-2) subsequence. A two-deletion correcting code requires at least 2 log n + O(1), while the best known explicit construction uses 4 log n + o(log n) redundant bits. In this work, we study this coding problem in the framework of the sequence reconstruction problem and require the receiver to uniquely reconstruct a codeword from any N>2 of its length-(n-2) subsequences. Specifically, we provide an explicit code construction that uniquely reconstructs a codeword from any five of its length-(n-2) subsequences, using only 2 log n + o(log n) redundant bits.