Sequence reconstruction problem for deletion channels: a complete asymptotic solution

• Main Authors: Pham, Van Long Phuoc, Goyal, Keshav, Kiah, Han Mao
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2025
• Subjects: Mathematical Sciences; Sequence reconstruction problem; Deletion-correcting codes
• Online Access: https://hdl.handle.net/10356/182329
• Institution: Nanyang Technological University

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.