Trace Reconstruction with Bounded Edit Distance

Jin Sima, Jehoshua Bruck

The trace reconstruction problem studies the number of noisy samples needed to recover an unknown string $\mathbf{x}\in \{0,1{\}}^n$ with high probability, where the samples are i…