Worst-case trace reconstruction

You have repeated damaged copies of one unknown bit string, and want to recover it exactly. Can the number of copies always be bounded by one fixed power of its length? Each copy independently loses each bit with probability one-half, without marking the missing positions.

If the original were 010, copies could include 010,10,01 or an empty string. A received 01 could also come from 001, so a single damaged copy need not identify the original. The required guarantee knows the original length n, must work for every n-bit string, and must succeed with probability at least two-thirds; computation time is unrestricted.[1] [2]

When every independently damaged copy hides its deleted positions, do a fixed-power number of copies suffice to identify every original string exactly? For 010 and 001, the output 01 has probabilities one-eighth and one-quarter: ambiguity of an outcome is distinct from equality of the full trace distributions.

For unknown $x\in\{0,1\}^n$ and known n, each trace independently retains each bit with probability one-half. Seek a decoder and fixed constants $A,k$ using $T(n)\leq A n^k$ traces with $\Pr[\widehat{x}=x]\geq 2/3$ for every x. Computation is unrestricted, and recovery must be exact. The term quasipolynomial describes a broader guarantee such as an exponential of a fixed power of log n; it does not by itself supply a fixed-power sample bound.[1] [2]

The July 2026 preprint gives a quasipolynomial bound on the number of copies. Its stated guarantee does not establish a fixed-power bound for every original. The missing step is a polynomial sample bound that works for every original. Evidence for random strings or specially selected messages has a different guarantee, and fast processing alone does not reduce the number of observations needed.[1] [2]

The July 2026 quasipolynomial-sample claim is a preprint advance and does not establish the polynomial target. It separates the number of observations from the cost of finding the whole original; the selected discussion does not furnish a quasipolynomial-time full reconstruction algorithm. Mean-statistic, random-input, approximate and circular-string results retain their distinct scopes.[1] [2]

The copies may disagree because different positions vanished, not because the underlying string changed. Aligning them therefore involves inferring where missing material belonged. The question asks whether repeated observations always contain enough information at a fixed-power sample scale, even before asking how quickly a decoder can process them.[1] [2]

The output probability for a survivor string counts its embeddings into the original, weighted by the deletion probabilities. Small statistical differences can therefore depend on global subsequence structure rather than just on average bit values at positions. This ties a combinatorial inverse problem to the amount of evidence needed for uniform statistical identification, before imposing computational efficiency.[1] [2]