Plectis Atlas
Search

↑ and ↓ move, Enter opens, Esc closes.

Show on the map

Quantitative trace-reconstruction bounds with a uniform decoder

OpenAI groups related papers into a “family”. OpenAI’s catalogue describes this one:

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. (OpenAI’s Lean note)

Lean is a language for mathematical statements and proofs that a computer can verify. The assessments below ask whether those statements express the result OpenAI describes here.

The independent assessments find that the Lean statements express only part of the result described above, or a narrower statement. Read the assessments

The paper states

Theorem 1.1 (Uniform trace reconstruction)

In Uniform quasipolynomial-time trace reconstruction, 5 October 2026

Possible match to OpenAI’s description, selected from the papers’ main statements because it shares the most wording. No review confirming the selection is recorded.

The other possible matches are Theorem 1.1 (Quantitative sample lower bound) in Quantitative lower bounds for trace reconstruction () and Theorem 1.2 (Superpolynomial one-trace indistinguishability) in Quantitative lower bounds for trace reconstruction ().

There exist absolute constants C,c\ge1 and one randomized multitape Turing machine \mathcal A with the following property. For every n\ge2, every rational p\in(0,1], and every x\in\{0,1\}^n, given n,p in binary and access to independent ordinary deletion traces of x, the machine requests at most

M_C(n,p)=\left\lceil\exp\bigl(CB(n,p)\bigr)\right\rceil

traces, outputs an element of \{0,1\}^n, and returns x with probability at least 2/3.

For every internal random-bit sequence and every well-formed trace stream of strings of length at most n, it halts within

\bigl(n+L+M_C(n,p)\bigr)^c

bit operations. This bound includes preprocessing, all parameter and finite-precision calculations, every received trace bit and delimiter, and the output. The only oracle operation is the external generation of the independent deletion traces.

No Lean statement in the release is paired with this theorem.

Reported proof verification
One Lean statement in the release; three independent groups report that Comparator accepted runs for this file at the version shown here.
Papers and explanations
Three current papers, each readable here as a page beside its PDF. One explanation by others.

Papers

Each paper opens as a reading page in the browser, with the PDF beside it. The statements each paper opens with are on its reading page.

Uniform quasipolynomial-time trace reconstruction

5 October 2026, current edition.

Read it herePDF

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.

A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction

5 October 2026, current edition.

Read it herePDF

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.

Quantitative lower bounds for trace reconstruction

24 September 2026, current edition.

Read it herePDF

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.

One Lean statement in this family

Lean is a language for mathematical statements and proofs that a computer can verify. The Lean statement below is shown beside its possible paper counterpart, with the reason they were linked.

For a configured theorem, the Comparator program tests whether OpenAI’s separate proof proves the exact Lean statement using only the allowed axioms. Some statement files instead configure definitions for comparison by name and type. Acceptance does not establish that a formal statement means the same thing as the paper’s theorem.

TraceReconstruction

The paper states

Theorem 1.1 (Quantitative sample lower bound)

In Quantitative lower bounds for trace reconstruction, 24 September 2026

Fix s\in(0,1] and 0<c<1/(4\log2). Along every sequence of instances (n,q) with n\to\infty, q\in(0,1), and q^3\log n\to\infty,

T_{q,s}(n)\ge n^{c\log(q^3\log n)}

eventually. All logarithms are natural. In particular, for each fixed deletion probability q\in(0,1) and fixed positive success probability s, the required sample number is n^{\Omega(\log\log n)}.

The words they share: quantitative, sample, natural, success, lower, bound, probability, deletion, log, reconstruction, trace, required, logarithms, eventually, number, sequence, along.

Possible Lean counterpart

Selected from shared wording. No review of whether the statements mean the same thing is recorded.

Quantitative and superpolynomial sample lower bounds for trace reconstruction

TraceReconstruction.lean, the release lists it as a supporting statement.

theorem quantitative_sample_lower_bound    (s c : ℝ) (hs : s ∈ Set.Ioc 0 1)    (hc : c ∈ Set.Ioo 0 (1 / (4 * Real.log 2)))    (n : ℕ → ℕ) (q : ℕ → ℝ)    (hn : Tendsto n atTop atTop)    (hq : ∀ k, q k ∈ Set.Ioo 0 1)    (hscale : Tendsto (fun k => (q k) ^ 3 * Real.log (n k)) atTop atTop) :    ∀ᶠ k in atTop,      ENNReal.ofReal ((n k : ℝ) ^ (c * Real.log ((q k) ^ 3 * Real.log (n k)))) ≤        sampleComplexity (n k) (q k) s := by  sorry

This file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.

The file states two more theorems: superpolynomial_one_trace, superpolynomial_sample_complexity.

three independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet; Neal McBurnett, openai-math-lean-tooling. Who ran the proof-verification program

  • cert-machine records it as “CERTIFIED”.
  • MathVet records it as “comparator-sandboxed-pass”.
  • Neal McBurnett, openai-math-lean-tooling records it as “accepted”.

Read the complete Lean statement

Other mathematical statements in OpenAI’s Lean library

Atlas found these propositions by scanning the text of the project’s Model.lean file. Each name links to its definition, with any associated statement file beside it. This list does not record running Lean to interpret or verify those definitions.

Independent comparisons and proof-verification reports

Does the Lean express the advertised result?

Neither group finds that the Lean statements express or imply the whole advertised result. They describe what the statements express in different terms.

MathVet and Carlos Toledo’s cert-machine independently assessed whether this family’s Lean statements express the whole result OpenAI describes in its catalogue. These are assessments of the family as a whole, not of each paper theorem separately.

MathVet finds that the Lean statements express part of the advertised result (their term: “partial”).

Their note: Only the lower bounds (superpolynomial and n^{c log(q^3 log n)}) are stated; the quasipolynomial uniform decoder and the polynomial small-deletion-probability regime are not.

Definitions the group asks readers to compare with the paper: sampleComplexity n q s := sInf {m | ∃ estimator A, IsEstimator A ∧ ∀ x, s ≤ reconstructionSuccess q A x} in ℝ≥0∞ (estimator = arbitrary map from m traces to a probability vector over words, success averaged exactly over deletion masks; standard)

“partial”, in their words: Only a special case is stated, or a co-equal headline claim has no challenge statement.

Their method: An independent, model-assisted, pre-referee reading of each family’s challenge statements against its headline claim under a published rubric (PROTOCOL.md), with its own Comparator runs per challenge.

Read the original assessment Read MathVet’s method

cert-machine finds that the Lean statements express a narrower statement than the advertised result (their term: “NARROWER — UNLINKED”).

The gap they name: The headline’s two upper-bound sentences (a uniform decoder with quasipolynomial sample and running-time bounds for fixed rational retention probability; polynomial bounds when the deletion probability is ≤ n^{-ε}) — the content of two of the family’s three manuscripts — are not stated by any challenge. Only the lower bounds are.

“NARROWER — UNLINKED”, in their words: The challenge statements state less than the headline; the missing part comes from a paper the Lean note does not link.

Their method: Every Comparator challenge re-run on Linux with nanoda switched on, decided by a preregistered rule.

Read the original assessment Read cert-machine’s method

OpenAI’s own note on what its Lean covers

The formalization proves superpolynomial sample lower bounds for exact worst-case reconstruction of binary words from independent deletion traces, with unrestricted computation and any fixed positive success probability. For every fixed deletion probability $q\in(0,1)$, sample complexity grows faster than every fixed power of the word length; the minimum total-variation distance between two one-trace laws decays faster than every inverse power.

More quantitatively, along sequences with $q^3\log n\to\infty$, the required number of samples is at least $n^{c\log(q^3\log n)}$ eventually for every fixed $0<c<1/(4\log2)$. All logarithms are natural.

AI-drafted comparisons, with no recorded human review

  • Quantitative and superpolynomial sample lower bounds for trace reconstruction TraceReconstruction

    Unreviewed AI draft: states a paper’s theorem as the paper does. States both headline theorems: the quantitative sample lower bound n^{c log(q³ log n)} and superpolynomial decay of the one-trace total-variation distance, hence superpolynomial sample complexity. The upper-bound algorithms of the family’s later papers are not part of it.

Who ran the proof-verification program?

These groups report running Comparator with the release’s Lean statement files. For a configured theorem, it verifies OpenAI’s separate proof against the exact statement; some files instead configure definitions for comparison by name and type. Each row is the named group’s report. Atlas has not repeated the runs.

These reports do not list the software versions, proof-verification programs, axioms, time or memory in separate fields. Any such details in a report’s prose are reproduced below.

Quantitative and superpolynomial sample lower bounds for trace reconstruction TraceReconstruction

Three reports, all at the release’s recorded version.

Reported byTheir wordTheir accountDateOriginal report
cert-machine“CERTIFIED”Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution.10 October 2026Original report
MathVet“comparator-sandboxed-pass”Re-run through Comparator in a sandboxed virtual machine: accepted.8 October 2026Original report
Neal McBurnett, openai-math-lean-tooling“accepted”Re-run through Comparator with Lean’s kernel: accepted (the check took 123 s; peak memory 6.4 GiB).11 October 2026Original report

Explanations by others

Explanations of this family written elsewhere, by the people named. Each is their own reading of the mathematics.

  • seaworld008, seaworld008/openai-math-top30: thirty selected families explained in Chinese, 7 October 2026. Source

    Chinese-language explainer for general readers, with a beginner’s section, a specialist section, background on why the problem was hard and a diagram; it ends by saying it paraphrases OpenAI’s summary and does not represent consensus.

What these papers cite in the release, and what cites them

These links come from the papers’ bibliographies. A citation records that one paper cites another; how each cited result is used has not been examined here.

Within this family

Papers elsewhere in the release that this family’s papers cite

This family’s papers cite no paper elsewhere in the release.

Papers elsewhere in the release that cite this family’s papers

No paper elsewhere in the release cites this family’s papers.

References outside the release

Each paper’s outside references are listed with it on its reading page, where each citation is placed. Every outside work cited in the release: References outside the release

Explain a result, compare statements or propose a correction

Atlas has no contributed explanation for this family yet. You can offer one with a GitHub account. You receive named credit and disclose any AI assistance.

Each button opens a GitHub form with this page and its source version filled in. Opening the form does not reserve the work.

Offer to write an explanationCompare the Lean statement with the paperSuggest a source attributionSuggest a change

What people have said

Commentary on this family by others, dated and credited. It is commentary, not a finding.

  • An unsigned public tier list, the OpenAI Math Tier List, classes it as a proof and rates its significance, if it holds up, as “Career-defining publication”. The page says that nothing on it is verified.

    Author not stated. Source

Questions awaiting review

Each item identifies a statement, definition or report that needs further review. Its link opens a GitHub form with the source version already recorded.

Read the Lean statement against the paper

  • An AI agent drafted an assessment of which part of the paper this Lean statement expresses. No named human review is recorded. Open the form

Identify the theorem the catalogue describes

  • Family 122 The theorem shown was selected from shared wording with OpenAI’s description. Atlas records no review confirming that it is the theorem the description means. Open the form

Address a question raised in an independent assessment

Compare the proposed paper and Lean matches

  • Family 122 Atlas records no review of whether each linked Lean statement and paper theorem mean the same thing. Open the form