arXiv:1905.03031 [math.PR]AbstractReferencesReviewsResources
New Lower Bounds for Trace Reconstruction
Published 2019-05-08Version 1
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^{16} 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)^{16}}\right)$.
Comments: 18 pages
Related articles: Most relevant | Search more
arXiv:1808.02336 [math.PR] (Published 2018-08-04)
Lower bounds for trace reconstruction
arXiv:1003.0334 [math.PR] (Published 2010-03-01)
A lower bound on the critical parameter of interlacement percolation in high dimension
arXiv:math/0702879 [math.PR] (Published 2007-02-28)
Lower bounds for the density of locally elliptic Itô processes