oai-math-revised beta

Browse › Theoretical computer science › 122 Quantitative trace-reconstruction bounds with a uniform decoder

Quantitative lower bounds for trace reconstruction

OpenAI · September 24, 2026

Lean

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

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 fixed $0\lt c\lt 1/(4\log2)$. Here q is the known deletion probability, and all logarithms are natural.

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.

Comments and discussion

Formalization

Possibly relevant literature (found by the agent, not checked)

  • Burudgunte, Valiant, Wang, New Bounds for Circular Trace Reconstruction (ITCS 2026, LIPIcs, doi:10.4230/LIPIcs.ITCS.2026.30; arXiv:2512.02412). Proves an $\tilde\Omega(n^5)$ lower bound for the circular variant using pairs of constant-sparse strings with nearly indistinguishable traces, a related lower-bound construction not cited in the paper's history section.

Digests and expositions

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:quantitative-lower-bounds-for-trace-reconstruction-September-24-2026,
  author = {{OpenAI}},
  title = {{Quantitative lower bounds for trace reconstruction}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf}{OAI:quantitative-lower-bounds-for-trace-reconstruction-September-24-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: