Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces

Xi Chen, Anindya De, Chin Ho Lee +2

In the standard trace reconstruction problem, the goal is to \emph{exactly} reconstruct an unknown source string $\mathsf{x}\in \{0,1{\}}^n$ from independent "traces", which are cop…