Trace reconstruction for the deletion channel

In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability $q$, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability?

The best lower bound known is of order $n^{1.25}$. Until 2016, the best upper bound available was exponential in the square root of $n$. With Fedor Nazarov, we improve the square root to a cube root using complex analysis (bounds for Littlewood polynomials on the unit circle). This upper bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, O’Donnell and Servedio). If the string $x$ is random and $q<1/2$, we can show a subpolynomial number of traces suffices by comparison to a biased random walk. (Joint work with Alex Zhai, FOCS 2017). With Nina Holden and Robin Pemantle (COLT 2018), we removed the restriction $q<1/2$ for random inputs.