New Lower Bounds for Trace Reconstruction

Abstract

We improve the lower bound on worst case trace reconstruction from $\Omega \left(\frac{n^{5/4}}{\sqrt{\log n}}\right)$ to $\Omega \left(\frac{n^{3/2}}{{\log }^{7}n}\right)$. As a consequence, we improve the lower bound on average case trace reconstruction from $\Omega \left(\frac{{\log }^{9/4}n}{\sqrt{\log \log n}}\right)$ to $\Omega \left(\frac{{\log }^{5/2}n}{(\log \log n{)}^7}\right)$.

arXiv comment20 pages