Browse › Theoretical computer science › 122 Quantitative trace-reconstruction bounds with a uniform decoder
A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give an improved worst-case sample bound for reconstructing a string from independent deletion traces, with its length and retention probability known. For each fixed retention probability, the number of traces is quasipolynomial: the logarithm of the sample budget is $O((\log n)^3(1+\log\log(2n))^6)$. If the deletion probability is at most $n^{-\varepsilon}$ for fixed ε > 0, polynomially many traces suffice. These bounds apply to binary strings and to strings of general symbols observed exactly. They concern sample complexity and do not assert an efficient reconstruction algorithm or matching optimality.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release / mathcommunity mirror, Lean scope note 122: Quantitative trace-reconstruction bounds with a uniform decoder (lean/docs/122.md, 2026-10-06). The family's Lean scope note lists only the companion lower-bound paper, so it does not cover this paper's sample upper bound. [family-level]
Related prior literature mentioned by others
- Arnav Burudgunte, Paul Valiant and Hongao Wang, Quasipolynomial Trace Reconstruction (arXiv:2607.04073v1, 2026-07-05). The AI Proved What? exposition identifies this earlier quasipolynomial sample upper bound as background to the family’s lower-bound and decoder claims. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Nazarov, Peres, Trace reconstruction with exp(O(n^{1/3})) samples (arXiv:1612.03599, STOC 2017). A source for the complex-analytic generating-function approach to the deletion channel, which this paper's induction on source-string generating functions uses but does not cite.
Digests and expositions
- AI Proved What?, Polynomially many traces? Lower and upper bounds for trace reconstruction (Episode 122, October 2026). This video and transcript explain the three papers’ claims, the multiscale lower-bound construction and moment-based decoder, and distinguish the lower-bound Lean scope from the upper bounds. [AI-generated per source] [family-level]
Elsewhere
- Emergent Mind: family 122
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction-October-5-2026,
author = {{OpenAI}},
title = {{A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction-October-5-2026/paper.pdf}{OAI:A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction-October-5-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/122.md. The Lean statements have not been checked by people against the paper's claims.
Family 122: Quantitative trace-reconstruction bounds with a uniform decoder
At every fixed deletion probability in $(0,1)$, reconstructing an arbitrary length-n binary string requires $n^{\Omega(\log\log n)}$ independent traces, ruling out polynomial-sample reconstruction. A uniform decoder achieves quasipolynomial sample and running-time bounds for known fixed rational retention probabilities. When the deletion probability is at most $n^{-\varepsilon}$ for fixed ε > 0, both bounds become polynomial in the input and parameter encoding.
Other papers in this family:
- Uniform quasipolynomial-time trace reconstruction · October 5, 2026
- Quantitative lower bounds for trace reconstruction · September 24, 2026