  The goal of the trace reconstruction problem is to recover a string
$x\in\{0,1\}^n$ given many independent {\em traces} of $x$, where a trace is a
subsequence obtained from deleting bits of $x$ independently with some given
probability $p\in [0,1).$ A recent result of Chase (STOC 2021) shows how $x$
can be determined (in exponential time) from $\exp(\widetilde{O}(n^{1/5}))$
traces. This is the state-of-the-art result on the sample complexity of trace
reconstruction.
  In this paper we consider two kinds of algorithms for the trace
reconstruction problem.
  Our first, and technically more involved, result shows that any $k$-mer-based
algorithm for trace reconstruction must use $\exp(\Omega(n^{1/5}))$ traces,
under the assumption that the estimator requires $poly(2^k, 1/\varepsilon)$
traces, thus establishing the optimality of this number of traces. The analysis
of this result also shows that the analysis technique used by Chase (STOC 2021)
is essentially tight, and hence new techniques are needed in order to improve
the worst-case upper bound.
  Our second, simple, result considers the performance of the Maximum
Likelihood Estimator (MLE), which specifically picks the source string that has
the maximum likelihood to generate the samples (traces). We show that the MLE
algorithm uses a nearly optimal number of traces, \ie, up to a factor of $n$ in
the number of samples needed for an optimal algorithm, and show that this
factor of $n$ loss may be necessary under general ``model estimation''
settings.
