Correcting Two Deletions with More Reads

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\geqslant 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.