Quantitative lower bounds for trace reconstruction

Exact worst-case reconstruction of a binary word from independent deletion traces requires $n^{\Omega (\log \log n)}$ samples for every fixed deletion probability $q\in (0,1)$, even with unrestricted computation and any fixed positive success probability. This gives a negative answer to the polynomial-sample question for binary trace reconstruction. More generally, when $q^3\log n\to \infty$, we prove a lower bound of $n^{c\log (q^3\log n)}$ samples for every fixed $0<c<1/(4\log 2)$. Here q is the known deletion probability, and all logarithms are natural.