New Lower Bounds for Trace Reconstruction
Zachary Chase · arXiv (Cornell University) · 2019
We improve the lower bound on worst case trace reconstruction from $Ω\left(\frac{n^{5/4}}{\sqrt{\log n}}\right)$ to $Ω\left(\frac{n^{3/2}}{\log^{7} n}\right)$. As a consequence, we improve the lower bound on average case trace reconstruction from $Ω\left(\frac{\log^{9/4}n}{\sqrt{\log\log n}}\right)$ to $Ω\left(\frac{\log^{5/2}n}{(\log\log n)^{7}}\right)$.