New upper bounds for trace reconstruction

Abstract

We show that any $n$-bit string can be recovered with high probability from $\exp (\tilde{O}(n^{1/5}))$ independent random subsequences.

arXiv comment16 pages

References in corpus (1)

• A new upper bound for separating words

Cited by in corpus (3)

• Efficient average-case population recovery in the presence of insertions and deletions
• Trace Reconstruction with Bounded Edit Distance
• Reconstructing Arbitrary Trees from Traces in the Tree Edit Distance Model