Trace reconstruction with $\exp( O( n^{1/3} ) )$ samples

Understand

In the trace reconstruction problem, an unknown bit string $x \in \{0,1\}^n$ is observed through the deletion channel, which deletes each bit of $x$ with some constant probability $q$, yielding a contracted string $\widetilde{x}$.

• How many independent copies of $\widetilde{x}$ are needed to reconstruct $x$ with high probability? Prior to this work, the best upper bound, due to Holenstein, Mitzenmacher, Panigrahy, and Wieder (2008), was $\exp(\widetilde{O}(n^{1/2}))$.
• We improve this bound to $\exp(O(n^{1/3}))$ using statistics of individual bits in the output and show that this bound is sharp in the restricted model where this is the only information used.
• Our method, that uses elementary complex analysis, can also handle insertions.