Near-Optimal Trace Reconstruction for Mildly Separated Strings

Anders Aamand, Allen Liu, Shyam Narayanan

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…