Optimal mean-based algorithms for trace reconstruction

Understand

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$.