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\log2)$. Here $q$ is the known deletion probability, and all logarithms are natural.