Sequence Reconstruction Problem for Deletion Channels: A Complete Asymptotic Solution

Abstract

Transmit a codeword $x$, that belongs to an $(\ell -1)$-deletion-correcting code of length $n$, over a $t$-deletion channel for some $1\le \ell \le t<n$. Levenshtein, in 2001, proposed the problem of determining $N(n,\ell ,t)+1$, the minimum number of distinct channel outputs required to uniquely reconstruct $x$. Prior to this work, $N(n,\ell ,t)$ is known only when $\ell \in \{1,2\}$. Here, we provide an asymptotically exact solution for all values of $\ell$ and $t$. Specifically, we show that $N(n,\ell ,t)=\left(\genfrac{}{}{0ex}{}{2\ell }{\ell }\right)/(t-\ell )!n^{t-\ell }-O(n^{t-\ell -1})$ and in the special instance where $\ell =t$, we show that $N(n,\ell ,\ell )=\left(\genfrac{}{}{0ex}{}{2\ell }{\ell }\right)$. We also provide a conjecture on the exact value of $N(n,\ell ,t)$ for all values of $n$, $\ell$, and $t$.