The number of traces needed for trace reconstruction
A trace of a string $x \in \{0, 1\}^n$ is the string left after each bit is deleted independently with probability $\frac12$; the positions deleted are not reported. Let $m(n)$ be the least $m$ such that some procedure recovers $x$ from $m$ independent traces with probability at least $0.9$, for every $x \in \{0, 1\}^n$. Nazarov and Peres, and independently De, O'Donnell and Servedio, proved $m(n) \le \exp(C n^{1/3})$, and Chase improved this to $m(n) \le \exp(n^{1/5} (\log n)^{C})$. In the other direction Chase, after Holden and Lyons, proved $m(n) \ge n^{3/2} (\log n)^{-16}$.
Problem. What is the growth rate of $m(n)$?
Source: V. I. Levenshtein, Efficient reconstruction of sequences (2001), for the setting; Green heard the problem from Y. Peres. Listed as Problem 92 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- PR
- Keywords
- deletion channel, sample complexity, trace reconstruction
- Literature checked
- Nov. 3, 2026 by clemens-admin
References
@article{levenshtein2001reconstruction,
author = {Levenshtein, Vladimir I.},
title = {Efficient reconstruction of sequences},
journal = {IEEE Transactions on Information Theory},
volume = {47},
number = {1},
pages = {2--22},
year = {2001},
doi = {10.1109/18.904499}
}
@inproceedings{nazarovperes2017trace,
author = {Nazarov, Fedor and Peres, Yuval},
title = {Trace reconstruction with $\exp(O(n^{1/3}))$ samples},
booktitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing},
pages = {1042--1046},
year = {2017},
doi = {10.1145/3055399.3055494}
}
@inproceedings{deodonnellservedio2017trace,
author = {De, Anindya and O'Donnell, Ryan and Servedio, Rocco A.},
title = {Optimal mean-based algorithms for trace reconstruction},
booktitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing},
pages = {1047--1056},
year = {2017},
doi = {10.1145/3055399.3055450}
}
@article{holdenlyons2020lower,
author = {Holden, Nina and Lyons, Russell},
title = {Lower bounds for trace reconstruction},
journal = {Annals of Applied Probability},
volume = {30},
number = {2},
pages = {503--525},
year = {2020},
doi = {10.1214/19-AAP1506}
}
@article{chase2021lower,
author = {Chase, Zachary},
title = {New lower bounds for trace reconstruction},
journal = {Annales de l'Institut Henri Poincar{\'e}, Probabilit{\'e}s et Statistiques},
volume = {57},
pages = {627--643},
year = {2021},
doi = {10.1214/20-AIHP1089}
}
@inproceedings{chase2021separating,
author = {Chase, Zachary},
title = {Separating words and trace reconstruction},
booktitle = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing},
pages = {21--31},
year = {2021},
doi = {10.1145/3406325.3451118}
}
@misc{bvw2026quasipolynomial,
author = {Burudgunte, Arnav and Valiant, Paul and Wang, Hongao},
title = {Quasipolynomial Trace Reconstruction},
year = {2026},
eprint = {2607.04073},
archivePrefix = {arXiv}
}
@misc{openai2026tracelower,
author = {{OpenAI}},
title = {Quantitative lower bounds for trace reconstruction},
howpublished = {\url{https://github.com/openai/math/blob/4eaee87548250b2682affda7d05d947c05554bae/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf}},
note = {AI-generated, unrefereed; dated 24 September 2026},
year = {2026}
}
@misc{openai2026traceupper,
author = {{OpenAI}},
title = {A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction},
howpublished = {\url{https://github.com/openai/math/blob/4eaee87548250b2682affda7d05d947c05554bae/preprints/A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction-October-5-2026/paper.pdf}},
note = {AI-generated, unrefereed; dated 5 October 2026},
year = {2026}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 92; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
Partial: for each fixed retention probability, log m(n) = O((log n)^3 (1 + log log 2n)^6), so quasipolynomially many traces suffice; success probability 2/3 is amplified to 0.9 by repetition..
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-11-08 | Open → Partially resolved | The registry's curators | A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction v1 recorded from math @ 4eaee87, build/main.tex. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01141, "The number of traces needed for trace reconstruction", clopen.solutions.