Optimal mean-based algorithms for trace reconstruction
  In the (deletion-channel) trace reconstruction problem, there is an unknown
$n$-bit source string $x$. An algorithm is given access to independent traces
of $x$, where a trace is formed by deleting each bit of~$x$ independently with
probability~$\delta$. The goal of the algorithm is to recover~$x$ exactly (with
high probability), while minimizing samples (number of traces) and running
time.
  Previously, the best known algorithm for the trace reconstruction problem was
due to Holenstein~et~al.; it uses $\exp(\tilde{O}(n^{1/2}))$ samples and
running time for any fixed $0 < \delta < 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^{\tilde{\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 $0 < \delta < 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 := 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 > 1/2$,
the presence of insertions can actually help with trace reconstruction.
