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. (Lean)
Manuscripts (3)
Uniform quasipolynomial-time trace reconstruction
October 5, 2026 · source · cite as \cite{OAI:Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026}
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
October 5, 2026 · source · cite as \cite{OAI:A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction-October-5-2026}
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
September 24, 2026 · source · cite as \cite{OAI:quantitative-lower-bounds-for-trace-reconstruction-September-24-2026}
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.
Result 122 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md