arXiv Analytics

Sign in

arXiv:1905.03031 [math.PR]AbstractReferencesReviewsResources

New Lower Bounds for Trace Reconstruction

Zachary Chase

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)$.

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