Lower bounds for trace reconstruction

Nina Holden, Russell Lyons

In the trace reconstruction problem, an unknown bit string $\mathbf{x}\in \{0,1{\}}^n$ is sent through a deletion channel where each bit is deleted independently with some probability $…