New upper 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

Zachary Chase This is my paper

classification math.PR cs.ITmath.COmath.IT

keywords boundshighindependentprobabilityrandomreconstructionrecoveredstring

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

read the original abstract

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

Forward citations

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The trace reconstruction problem for spider graphs
cs.DS 2022-09 unverdicted novelty 6.0

An algorithm reconstructs spider graphs with high probability from exp(O((n q^d)^{1/3} d^{-1/3} (log n)^{2/3})) deletion traces when leg length d is at most log base 1/q of n.