Sequence reconstruction problem for deletion channels: a complete asymptotic solution

Abstract

Transmit a codeword x, that belongs to an (ℓ−1)-deletion-correcting code of length n, over a t-deletion channel for some 1≤ℓ≤t<n. Levenshtein (2001) [10], proposed the problem of determining N(n,ℓ,t)+1, the minimum number of distinct channel outputs required to uniquely reconstruct x. Prior to this work, N(n,ℓ,t) is known only when ℓ∈{1,2}. Here, we provide an asymptotically exact solution for all values of ℓ and t. Specifically, we show that [Formula presented]. In the special instances: where ℓ=t, we show that N(n,ℓ,ℓ)=(2ℓℓ); and when ℓ=3 and t=4, we show that N(n,3,4)≤20n−150. We also provide a conjecture on the exact value of N(n,ℓ,t) for all values of n, ℓ, and t.