REVIEW 1 cited by
New Lower Bounds for Trace Reconstruction
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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)$.
Forward citations
Cited by 1 Pith paper
-
A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
Worst-case probability strings require e^{Ω(√n)} traces to distinguish under deletions, while random probability strings are recoverable to ℓ1 error ε with poly(n,1/ε) traces.
Discussion (0). Continue with ORCID to comment.