  The trace reconstruction problem studies the number of noisy samples needed
to recover an unknown string $\boldsymbol{x}\in\{0,1\}^n$ with high
probability, where the samples are independently obtained by passing
$\boldsymbol{x}$ through a random deletion channel with deletion probability
$q$. The problem is receiving significant attention recently due to its
applications in DNA sequencing and DNA storage. Yet, there is still an
exponential gap between upper and lower bounds for the trace reconstruction
problem. In this paper we study the trace reconstruction problem when
$\boldsymbol{x}$ is confined to an edit distance ball of radius $k$, which is
essentially equivalent to distinguishing two strings with edit distance at most
$k$. It is shown that $n^{O(k)}$ samples suffice to achieve this task with high
probability.
