oai-math-revised beta

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

Uniform quasipolynomial-time trace reconstruction

OpenAI · October 5, 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

We give a uniform algorithm that reconstructs every binary string from independent deletion traces when its length and rational retention probability are known. For each fixed retention probability, both the number of traces and the bit complexity are quasipolynomial in the string length. More generally, we give an explicit sample bound uniform over all rational retention probabilities, with running time polynomial in the sample budget and the binary input length. If the deletion probability is at most $n^{-\varepsilon}$ for fixed ε > 0, the sample and running-time bounds are polynomial. Reconstruction succeeds with probability at least 2/3 for each input string.

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

Digests and expositions

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026,
  author = {{OpenAI}},
  title = {{Uniform quasipolynomial-time trace reconstruction}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf}{OAI:Uniform-quasipolynomial-time-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: