Near-Optimal Trace Reconstruction for Mildly Separated Strings

In the trace reconstruction problem our goal is to learn an unknown string $x\in \{0,1{\}}^n$ given independent traces of $x$. A trace is obtained by independently deleting each bit of $x$ with some probability $\delta$ and concatenating the remaining bits. It is a major open question whether the trace reconstruction problem can be solved with a polynomial number of traces when the deletion probability $\delta$ is constant. The best known upper bound and lower bounds are respectively $\exp (\tilde{O}(n^{1\mathrm{/}5}))$ and $\tilde{\mathrm{\Omega }}(n^{3\mathrm{/}2})$ both by Chase [Cha21b,Cha21a]. Our main result is that if the string $x$ is mildly separated, meaning that the number of zeros between any two ones in $x$ is at least polylog$n$, and if $\delta$ is a sufficiently small constant, then the trace reconstruction problem can be solved with $O(n\log n)$ traces and in polynomial time.