REVIEW 2 cited by
Approximate trace reconstruction of random strings from a constant number of traces
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
In the trace reconstruction problem, the goal is to reconstruct an unknown string $x$ of length $n$ from multiple traces obtained by passing $x$ through the deletion channel. In the relaxed problem of $approximate$ trace reconstruction, the goal is to reconstruct an approximation $\widehat{x}$ of $x$ which is close (within $\epsilon n$) to $x$ in edit distance. We show that for most strings $x$, this is possible with high probability using only a constant number of traces. Crucially, this constant does not grow with $n$, and only depends on the deletion probability and $\epsilon$.
Forward citations
Cited by 2 Pith papers
-
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.
-
Near-Optimal Trace Reconstruction for Mildly Separated Strings
A near-optimal trace reconstruction algorithm uses O(n log n) traces and polynomial time for strings whose 1s are separated by polylog n zeros, under small constant deletion probability.
Discussion (0). Continue with ORCID to comment.