Trace reconstruction from deletion channels
From OpenAI Aftermath
Trace reconstruction asks how many independent traces of an unknown binary string of length n are needed to recover it, where a trace is obtained by deleting each bit independently with a known probability q and concatenating the surviving bits in order. For a fixed deletion probability and worst-case strings, the best upper bounds came down from eÕ(√n) to eO(n1/5 log5 n), and a 2026 preprint of Burudgunte, Valiant and Wang reached a quasipolynomial number of traces, while the known lower bounds were polynomial. Three manuscripts in OpenAI's public mathematics collection (github.com/openai/math), listed together as its result 122, claim that nΩ(log log n) traces are necessary at every fixed deletion probability, so that polynomially many traces never suffice, and give a uniform quasipolynomial-time decoder and a sharper quasipolynomial sample bound. The collection includes a Lean formalization of the lower bounds.
Background
- As recounted in the introductions of the manuscripts:
- Levenshtein studied the reconstruction of sequences from repeated corrupted observations, and Batu, Kannan, Khanna and McGregor studied the independent-deletion trace problem in connection with multiple sequence alignment.
- For a fixed deletion probability, Holenstein, Mitzenmacher, Panigrahy and Wieder obtained the worst-case upper bound eÕ(√n); De, O'Donnell and Servedio and, independently, Nazarov and Peres improved it to eO(n1/3); and Chase obtained eO(n1/5 log5 n). The 2026 preprint of Burudgunte, Valiant and Wang gives a quasipolynomial number of samples at every fixed retention probability, with an unspecified power of log n, and no quasipolynomial-time algorithm.
- Polynomial reconstruction is known under other conditions, for example for deletion probabilities at most n−1/3−ε by Chen, De, Lee, Servedio and Sinha. Earlier lower bounds for complete traces were polynomial, and some lower bounds concern restricted statistics rather than complete traces.
The original results
- Claim, lower bound. Theorem 1.1 of Quantitative lower bounds for trace reconstruction states that along every sequence of instances with q3 log n → ∞, exact worst-case reconstruction of binary words with any fixed positive success probability, even with unrestricted computation, eventually needs at least nc log(q3 log n) traces for every fixed 0 < c < 1/(4 log 2); at a fixed deletion probability this is nΩ(log log n). A second theorem states that the minimum total-variation distance between the one-trace laws of two distinct strings of length n decays faster than every inverse power of n.
- Method, as described: the construction hides differences in location at several scales, using runs whose trace laws share an exact common mass to create binomial uncertainty in the position of a central segment, and complementary Prouhet–Thue–Morse sign patterns whose generating polynomial vanishes to high order at 1.
- Claim, uniform decoder. Theorem 1.1 of Uniform quasipolynomial-time trace reconstruction states that one randomized Turing machine, given n and a rational retention probability p, reconstructs every binary string of length n with probability at least 2/3 from an explicit number of traces; at every fixed p both the number of traces and the bit complexity are quasipolynomial in n, and they become polynomial when the deletion probability is at most n−ε.
- Claim, sample bound. Theorem 1 of A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction states that at every fixed retention probability the logarithm of the sample budget is O((log n)3(1 + log log 2n)6), for binary strings and for strings of general symbols observed exactly, and that polynomially many traces suffice when the deletion probability is at most n−ε. The manuscript states that this concerns sample complexity only and does not assert an efficient algorithm or optimality.
- Formalization, as described by the repository. The scope note links only the lower-bound manuscript and states that the formalization proves superpolynomial sample lower bounds for exact worst-case reconstruction with unrestricted computation and any fixed positive success probability, the faster-than-polynomial decay of the minimum one-trace total-variation distance, and the quantitative bound along sequences with q3 log n → ∞. The Comparator statement is
TraceReconstruction.lean. - Sources (openai/math repository, commit
7ef5c0c): Quantitative lower bounds for trace reconstruction, dated 24 September 2026; Uniform quasipolynomial-time trace reconstruction and A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction, both dated 5 October 2026.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 30 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | Deletion traces: sample lower bounds and uniform reconstruction, an article of the Latent Seminar blog at lowrank.github.io | Reading (exposition) | Explains the three contributions: the superpolynomial sample lower bound with one-trace indistinguishability, the uniform quasipolynomial decoder, and the sharper quasipolynomial sample bound, with the polynomial regime for small deletion probabilities. It describes how generating functions expose the hidden positions, the latest-anchor induction with compact frequency masks, the passage from pair separation to an efficient decoder, and the lower-bound construction. | Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit c76f1e4, 14 October 2026) |
Review (fidelity of the formal statements) | Rates this family "partial" and records a sandboxed Comparator pass for TraceReconstruction. Its note states that only the lower bounds are formalized and that the quasipolynomial uniform decoder and the polynomial regime for small deletion probabilities are not. It lists the definition of sample complexity, an infimum over arbitrary estimators with success averaged exactly over deletion masks, as standard. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K, run 38040214623 | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the TraceReconstruction solution, in 478 s. C. Toledo's report lists the challenge among those certified by both kernels. |
Repository. The run concerns the formalized lower bounds only. |
| 2026-10-16 | J. Jardine, Lattice24, referee reviews rank_512 (lower bound), rank_528 (uniform decoder) and rank_495 (latest-anchor sample bound) in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | All three reviews report no gap. Each states that it read every section and lists the steps it checked, with some numerical constants recomputed. The review of the latest-anchor manuscript records one minor issue: the bound on the entire continuation in the radial compactification step is only sketched, which it describes as the least explicitly verified step, without an identified error. | Part of an audit of the collection's manuscripts that the audit describes as complete. The reviews are published under CC BY 4.0. |
| 2026-10-16 | AI Proved What?, episode 122 Polynomially many traces?, remade version of 26 October 2026 | Reading (exposition) | Video explainer of the three claims: at every fixed deletion probability, exact reconstruction of every binary string of length n needs more than n to the power c log of q cubed log n traces for every c below 1 over 4 log 2, that is n to the power Ω of log log n, even with unlimited computation, so polynomially many traces never suffice, and some distinct strings have single-trace laws closer than any fixed inverse power of n; one randomized algorithm that, knowing n and a rational retention probability, recovers any string with probability at least 2/3 from a quasipolynomial number of traces with quasipolynomial bit complexity, polynomial when the deletion probability is at most n to the power minus ε; and the same sample bound for general symbols without an efficient algorithm. The episode states that the lower bound concerns growth, passing Chase's exponent 3/2 at deletion probability 1/2 only for n with more than 220 digits, that a gap remains between the bounds, and that the decoder needs the retention probability as a known rational number. | Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as preprints: OpenAI, three preprints of 42 pages dated September 24, 2026 and of 29 and 15 pages dated October 5, 2026; under expert review: not yet; peer reviewed: not yet; checked in Lean: the lower bounds, not the upper bounds; the site has not run the check. The page states that the preprints have not been revised, that the Lean formalization of the lower bounds, stated for every estimator with unlimited computation, has 31 files and 33,984 lines with its imports and no unproved steps that the site could find, that none of the papers is among those OSVerify reviewed, and that it has seen no expert review. |
Notes
- The background summarizes the manuscripts' own account of earlier work.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
