Polynomial sample complexity for deletion-trace reconstruction
Fix a known deletion probability $q \in (0,1)$. A trace of an unknown string $x \in \{0,1\}^n$ of known length $n$ is obtained by deleting each bit independently with probability $q$ and concatenating the retained bits in their original order; the deleted positions are not reported. Write $D_q(x)$ for the law of a trace, a distribution on the binary strings of length at most $n$, the empty string included. A decoder $A_{n,q}$ maps $m$ traces to $\{0,1\}^n$; it may use its own randomness, its computation is unrestricted, and it must be the same for every string of length $n$. For fixed $q$, Chase proved that recovering every string requires $\Omega(n^{3/2}/\log^7 n)$ traces, and that $\exp(\tilde O(n^{1/5}))$ traces suffice; Burudgunte, Valiant and Wang proved that a quasipolynomial number of traces suffices.
Problem. For every fixed $q \in (0,1)$, do there exist finite constants $C_q, k_q > 0$ such that, for every $n \ge 2$, some decoder $A_{n,q}$ using $m \le \lceil C_q n^{k_q} \rceil$ independent traces satisfies $$\inf_{x \in \{0,1\}^n} \Pr\bigl[A_{n,q}(Y_1, \dots, Y_m) = x\bigr] \ge \frac23, \qquad Y_1, \dots, Y_m \overset{\mathrm{iid}}{\sim} D_q(x)?$$ The probability includes the decoder's randomness and all deletions.
Source: A long-standing question in trace reconstruction, whether polynomially many traces suffice at constant deletion probability (see Aamand, Liu and Narayanan (2025), abstract); stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- IT, ST
- Keywords
- AIM Open Applied Problems, deletion channel, sample complexity, trace reconstruction
References
@inproceedings{aamand2025,
author = {Aamand, Anders and Liu, Allen and Narayanan, Shyam},
title = {Near-Optimal Trace Reconstruction for Mildly Separated Strings},
booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
series = {LIPIcs},
volume = {334},
year = {2025},
pages = {3:1--3:20},
doi = {10.4230/LIPIcs.ICALP.2025.3},
eprint = {2411.18765},
archivePrefix = {arXiv},
}
@article{chase2021lower,
author = {Chase, Zachary},
title = {New lower bounds for trace reconstruction},
journal = {Ann. Inst. Henri Poincar{\'e} Probab. Stat.},
volume = {57},
number = {2},
year = {2021},
pages = {627--643},
doi = {10.1214/20-AIHP1089},
eprint = {1905.03031},
archivePrefix = {arXiv},
}
@inproceedings{chase2021upper,
author = {Chase, Zachary},
title = {Separating words and trace reconstruction},
booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)},
publisher = {ACM},
year = {2021},
pages = {21--31},
doi = {10.1145/3406325.3451118},
}
@misc{burudgunte2026,
author = {Burudgunte, Arnav and Valiant, Paul and Wang, Hongao},
title = {Quasipolynomial Trace Reconstruction},
year = {2026},
eprint = {2607.04073},
archivePrefix = {arXiv},
}
@misc{aim-polynomial-trace-reconstruction,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial sample complexity for deletion-trace reconstruction}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/1b7c7fd251c1643bb41f0e3cef38704bcef410fd/problems/321-polynomial-trace-reconstruction.md},
note = {Entry 321 at commit 1b7c7fd, 2026-10-13},
}
Resolution claims
Exact worst-case reconstruction of a binary word from independent deletion traces requires $n^{\Omega(\log\log n)}$ samples for every fixed deletion probability $q\in(0,1)$, even with unrestricted computation and any fixed positive success probability. This gives a negative answer to the polynomial-sample question for binary trace reconstruction. More generally, when $q^3\log n\to\infty$, we prove a lower bound of $n^{c\log(q^3\log n)}$ samples for every …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: math @ 1581d4c, build/main.tex. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00705, "Polynomial sample complexity for deletion-trace reconstruction", clopen.solutions.