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}$. When the input is drawn uniformly at random, we...