Optimal mean-based algorithms for trace reconstruction

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 ..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. [in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms 389.398 (2008) ACM]; it uses exp(O.(n1/2)) exp samples and running time for any fixed 0<.<1.It is also what we call a .mean-based algorithm,. meaning that it only uses the empirical means of the individual bits of the traces.Holenstein et al. also gave a lower bound, showing that any mean-based algorithm must use at least n..(long) samples.In this paper, we improve both of these results, obtaining matching upper and lower bounds for mean-based trace reconstruction.For any constant deletion rate 0<.<, we give a mean-based algorithm that uses exp(O(n1/3)) exp time and traces; we also prove that any mean-based algorithm must use at least exp(.(n1/3)) exp traces.In fact, we obtain matching upper and lower bounds even for . subconstant and .=1.. subconstant: when (log3n)/n...1/2 the bound is exp(..(.n)1/3) exp, and when 1/n.....1/2 the bound is exp(..(n/.)1/3) exp.Our proofs involve estimates for the maxima of Littlewood polynomials on complex disks.We show that these techniques can also be used to perform trace reconstruction with random insertions and bit-flips in addition to deletions.We also find a surprising result: for deletion probabilities .>1/2, the presence of insertions can actually help with trace reconstruction.