Lower bounds for trace reconstruction

Nina Holden, Russell Lyons

Published 2018-08-04Version 1

In the trace reconstruction problem, an unknown bit string ${\bf x}\in\{0,1\}^n$ is sent through a deletion channel where each bit is deleted independently with some probability $q\in(0,1)$, yielding a contracted string $\widetilde{\bf x}$. How many i.i.d. samples of $\widetilde{\bf x}$ are needed to reconstruct ${\bf x}$ with high probability? We prove that there exist ${\bf x},{\bf y}\in\{0,1 \}^n$ such that we need at least $c\, n^{5/4}/\sqrt{\log n}$ traces to distinguish between ${\bf x}$ and ${\bf y}$ for some absolute constant $c$, improving the previous lower bound of $c\,n$. Furthermore, our result improves the previously known lower bound for reconstruction of random strings from $c \log^2 n$ to $c \log^{9/4}n/\sqrt{\log \log n} $.