Trace Reconstruction

Trace reconstruction is the problem of recovering an unknown string from independently generated copies in which each symbol is independently deleted with a specified probability. Each resulting trace gives the surviving symbols in their original order but not their original positions. The original length and the channel's retention probability are assumed known, and the recovery guarantee must hold separately for every input string.