text: abstract
  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 holene 1/2 )) samples and running time for any fixed 0 < δ < 1.
  stein et al. [hmpw08]; it uses exp(o(n
  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
  e
  mean-based algorithm must use at least nω(log n) 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 < δ < 1, we give a meanbased algorithm that uses exp(o(n1/3 )) time and traces; we also prove that any mean-based
  algorithm must use at least exp(ω(n1/3 )) traces. in fact, we obtain matching upper and lower
  bounds even for δ subconstant and ρ :=
  1 − δ subconstant: when (log3 n)/n ≪ δ ≤ 1/2 the
  √
  bound is exp(−θ(δn)1/3 ), and when 1/ n ≪ ρ ≤ 1/2 the bound is exp(−θ(n/ρ)1/3 ).
  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.