Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance

Elena Grigorescu, Madhu Sudan, Minshen Zhu

Trace reconstruction considers the task of recovering an unknown string $x\in \{0,1{\}}^n$ given a number of independent "traces", i.e., subsequences of $x$ obtained by randomly and…