Previously, the best known algorithm for the trace reconstruction problem was due to Holenstein et al. \cite{HMPW08}; it uses $\exp(\wt{O}(n^{1/2}))$ samples and running time for any fixed $\delta\in (0,1)$. It is also what we call a ``mean-based algorithm'', meaning that it only uses the empirical means of the individual bits of the traces. Holenstein et al. also gave a lower bound, showing that any mean-based algorithm must use at least $n^{\wt{\Omega}(\log n)}$ samples.
In this paper we improve both of these results, obtaining matching upper and lower bounds for mean-based trace reconstruction. For any constant deletion rate $\delta \in (0,1)$, we give a mean-based algorithm that uses $\exp(O(n^{1/3}))$ time and traces; we also prove that any mean-based algorithm must use at least $\exp(\Omega(n^{1/3}))$ traces. In fact, we obtain matching upper and lower bounds even for $\delta$ subconstant and $\rho \coloneqq 1-\delta$ subconstant: when $(\log^3 n)/n \ll \delta \leq 1/2$ the bound is $\exp(-\Theta(\delta n)^{1/3})$, and when $1/\sqrt{n} \ll \rho \leq 1/2$ the bound is $\exp(-\Theta(n/\rho)^{1/3})$.
Our proofs involve estimates for the maxima of Littlewood polynomials on complex disks. We show that these techniques can also be used to perform trace reconstruction with random insertions and bit-flips in addition to deletions. We also find a surprising result: for deletion probabilities $\delta$ larger than $1/2$, the presence of insertions can actually \emph{help} with trace reconstruction.