  The deletion channel takes as input a bit string $\mathbf{x} \in \{0,1\}^n$,
and deletes each bit independently with probability $q$, yielding a shorter
string. The trace reconstruction problem is to recover an unknown string
$\mathbf{x}$ from many independent outputs (called "traces") of the deletion
channel applied to $\mathbf{x}$. We show that if $\mathbf{x}$ is drawn
uniformly at random and $q < 1/2$, then $e^{O(\log^{1/2} n)}$ traces suffice to
reconstruct $\mathbf{x}$ with high probability. The previous best bound,
established in 2008 by Holenstein-Mitzenmacher-Panigrahy-Wieder, uses
$n^{O(1)}$ traces and only applies for $q$ less than a smaller threshold (it
seems that $q < 0.07$ is needed). Our algorithm combines several ideas: 1) an
alignment scheme for "greedily" fitting the output of the deletion channel as a
subsequence of the input; 2) a version of the idea of "anchoring" used by
Holenstein-Mitzenmacher-Panigrahy-Wieder; and 3) complex analysis techniques
from recent work of Nazarov-Peres and De-O'Donnell-Servedio.
