Quantitative trace-reconstruction bounds with a uniform decoder

Rebuilding a string from randomly thinned copies needs more than polynomially many copies.

3 papers September 24, 2026 Explained by AI

A channel deletes each bit of a hidden string at random. You must rebuild the string from many such copies. One paper proves that at a fixed deletion rate, some strings need more copies than any power of the length. A second paper claims to give one algorithm that rebuilds every string with a quasipolynomial number of copies and steps. A third claims a smaller quasipolynomial copy count, without a fast algorithm.

First step

2004

Batu, Kannan, Khanna and McGregor, independent-deletion trace problem

Significance

Major

If the proofs hold, they answer the polynomial-sample question and add a quasipolynomial-time algorithm.

Trust

Formal proof listed

Field

Theoretical computer science

3 papers

Best proven lower bound on traces needed, as a power of n

Year	Who	Value
2004	Batu, Kannan, Khanna and McGregor (outlined)	1
2020	Holden and Lyons	1.25
2021	Chase	1.5

Higher is stronger. Log factors are dropped. The new bound beats every fixed power, so it has no single value here.

The explanation

Take the string 0110 and pass it through a noisy channel. The channel deletes each bit on its own, with chance 1/2. What comes out is a trace: the surviving bits, in order, with their positions lost. All 16 keep-or-delete patterns are equally likely. The trace 01 comes out in 2 of them, so its chance is 1/8. The full string 0110 survives intact only 1 time in 16. Trace reconstruction asks you to name the original string from many such traces. The hard version asks this for every possible string, not just typical ones.

Some pairs of strings are hard to tell apart. Compare 0100 with 0010, where one lone 1 has moved one place. From a single trace, the best possible guess is right about 59.4% of the time. For 00010000 against 00001000 it drops to about 56.8%. A full search over every pair of length 8 finds none harder at this deletion rate. More traces sharpen the guess. The real question is how fast the number of traces needed must grow with the length n.

Two kinds of growth matter here. Polynomial growth means a fixed power of n, such as n² or n¹⁰. Quasipolynomial growth is faster than every fixed power, yet far slower than exponential growth like 2 to the power n. Batu, Kannan, Khanna and McGregor set out this problem in 2004 and sketched why about n traces are needed. Known upper limits then fell. They went from exp of roughly √n in 2008 to exp of about n to the 1/5 in 2021. Here exp means the number e raised to that power. The best lower limits reached about n to the 3/2. In 2026 Burudgunte, Valiant and Wang showed that quasipolynomially many traces suffice at a fixed deletion rate. Two things were still open. Could a polynomial number of traces ever be enough? And could a fast method actually find the string?

The September paper answers the first question with noSource 1. Fix any deletion rate. It proves that some strings then need at least n to the power (constant × log log n) traces. Here log log n means the logarithm taken twice, so it grows without limit, though very slowly. That makes the requirement outgrow every fixed power of n. The bound holds even with unlimited computing power and any fixed chance of successSource 2. The paper also proves a sharper form when the deletion rate may shrink as n growsSource 3.

The obstacle for lower bounds was building two strings whose traces stay almost identicalSource 4. Earlier pairs, like the lone shifted 1 above, differ in one place, and enough traces eventually reveal where. The new pairs hide their difference in location at many scales at onceSource 5. Their middle parts use opposite plus-and-minus patterns from the Thue–Morse sequence, a classic pattern that cancels itself out wellSource 6 Source 7. When deletions blur positions, those opposite patterns cancel almost completely.

The two October papers work on the other side. One claims to give a single algorithm that reconstructs every string when n and a rational keep-probability are knownSource 8. For each fixed rate, both its trace count and its running time are quasipolynomial in nSource 9. It succeeds with chance at least 2/3 for each stringSource 10. It finds the answer one bit at a time, instead of searching over every possible stringSource 11 Source 12. That matters because the 2026 sample bound came with no fast reconstruction method. The other October paper claims a smaller quasipolynomial trace count, but gives no efficient algorithmSource 13. Both claim polynomial trace counts when the deletion rate is at most 1/n^ε, for some fixed ε above 0Source 14.

So the polynomial hope is gone, but the exact answer is not known. The logarithm of the lower bound grows like log n times log log n. The logarithm of the upper bound grows like a fixed power of log n. These two rates still leave a gapSource 15. The results also describe growth as n becomes large. They do not say how many traces the length-8 pair above needs.

How sure is this? A computer proof checker called Lean has checked formal versions of the lower bounds from the September paper. That covers the faster-than-every-power requirement at each fixed deletion rate and the sharper quantitative form. The two October papers, with the algorithm and the trace counts, are outside that check. No specialist review of any of the three papers has been published.

What it doesn't show. This does not settle the exact number of copies needed, since the lower and upper bounds still differ.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Important if the proofs hold. Only the lower bounds have a Lean check. The algorithm and trace counts in the two October papers are not machine-checked. No specialist review is published. The exact growth rate is still open.

Words used

Trace: What survives when each bit of a string is deleted at random: the kept bits in order, without their positions.
Trace reconstruction: Recovering the original string from many independent traces.
Deletion rate: The chance that the channel deletes any one bit. The keep-probability is one minus this.
Polynomial growth: Growth no faster than a fixed power of n, such as n squared.
Quasipolynomial growth: Growth faster than every fixed power of n but far slower than exponential growth; roughly e raised to a power of log n.
Worst case: The method must succeed for every possible input string, not just typical ones.
Thue–Morse sequence: A classic sequence of 0s and 1s built by repeatedly appending the flipped copy; its plus-and-minus version cancels out well.

The original papers (3)

Uniform quasipolynomial-time trace reconstruction (PDF, opens in a new tab)
October 5, 2026
A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction (PDF, opens in a new tab)
October 5, 2026
Quantitative lower bounds for trace reconstruction (PDF, opens in a new tab)
September 24, 2026

Lean notes

All quoted lines (15)

This gives a negative answer to the polynomial-sample question for binary trace reconstruction.
Quantitative lower bounds for trace reconstruction Back to text
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.
Quantitative lower bounds for trace reconstruction Back to text
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<c<1/(4\log2)$ .
Quantitative lower bounds for trace reconstruction Back to text
Later lower bounds for complete traces focused on the difficulty of locating a small discrepancy within a long background.
Quantitative lower bounds for trace reconstruction Back to text
Our construction hides differences in location at several scales.
Quantitative lower bounds for trace reconstruction Back to text
The two words use complementary signed patterns in their central segments.
Quantitative lower bounds for trace reconstruction Back to text
The generating polynomial of a Prouhet–Thue–Morse pattern vanishes to high order at $1$ , making its convolution with a broad binomial offset small.
Quantitative lower bounds for trace reconstruction Back to text
We give a uniform algorithm that reconstructs every binary string from independent deletion traces when its length and rational retention probability are known.
Uniform quasipolynomial-time trace reconstruction Back to text
For each fixed retention probability, both the number of traces and the bit complexity are quasipolynomial in the string length.
Uniform quasipolynomial-time trace reconstruction Back to text
Reconstruction succeeds with probability at least $2/3$ for each input string.
Uniform quasipolynomial-time trace reconstruction Back to text
The resulting tests determine one bit at a time and can be implemented using rational arithmetic.
Uniform quasipolynomial-time trace reconstruction Back to text
It enables constructive feasibility tests in place of a search over complete strings.
Uniform quasipolynomial-time trace reconstruction Back to text
They concern sample complexity and do not assert an efficient reconstruction algorithm or matching optimality.
A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction Back to text
If the deletion probability is at most $n^{-\varepsilon}$ for fixed $\varepsilon>0$ , the sample and running-time bounds are polynomial.
Uniform quasipolynomial-time trace reconstruction Back to text
The logarithm of this sample bound is a fixed power of $\log n$ , whereas the logarithm of our lower bound at a fixed channel has order $(\log n)(\log\log n)$ , leaving a gap between the rates.
Quantitative lower bounds for trace reconstruction Back to text