Near-Optimal Trace Reconstruction for Mildly Separated Strings

Abstract

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 $\hat{I}´$ 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 $\hat{I}´$ is constant. The best known upper bound and lower bounds are respectively $\exp (\tilde{O}(n^{1/5}))$ and $\tilde{\hat{I}}\text{c◯}(n^{3/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 $\hat{I}´$ is a sufficiently small constant, then the trace reconstruction problem can be solved with $O(n\log n)$ traces and in polynomial time.