# Quantitative trace-reconstruction bounds with a uniform decoder > Rebuilding a string from randomly thinned copies needs more than polynomially many copies. Plain-English explainer, Lean status and sources. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-122/ Last updated: 2026-10-11 **Rebuilding a string from randomly thinned copies needs more than polynomially many copies.** **Trust:** Formal proof listed · **Papers:** 3 · **First paper:** September 24, 2026 · **Field:** Theoretical computer science · **Entry:** 122 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. 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. ## At a glance - **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 no[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 success[2]. The paper also proves a sharper form when the deletion rate may shrink as n grows[3]. The obstacle for lower bounds was building two strings whose traces stay almost identical[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 once[5]. Their middle parts use opposite plus-and-minus patterns from the Thue–Morse sequence, a classic pattern that cancels itself out well[6,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 known[8]. For each fixed rate, both its trace count and its running time are quasipolynomial in n[9]. It succeeds with chance at least 2/3 for each string[10]. It finds the answer one bit at a time, instead of searching over every possible string[11,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 algorithm[13]. Both claim polynomial trace counts when the deletion rate is at most 1/n^ε, for some fixed ε above 0[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 gap[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](https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf) - October 5, 2026 - [A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction](https://github.com/openai/math/blob/main/preprints/A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction-October-5-2026/paper.pdf) - October 5, 2026 - [Quantitative lower bounds for trace reconstruction](https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf) - September 24, 2026 - [Lean notes](https://github.com/openai/math/blob/main/lean/docs/122.md) ## Quoted lines from the paper (15) [1] From [Quantitative lower bounds for trace reconstruction](https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf): > This gives a negative answer to the polynomial-sample question for binary trace reconstruction. [2] From [Quantitative lower bounds for trace reconstruction](https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf): > 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. [3] From [Quantitative lower bounds for trace reconstruction](https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf): > 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 Later lower bounds for complete traces focused on the difficulty of locating a small discrepancy within a long background. [5] From [Quantitative lower bounds for trace reconstruction](https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf): > Our construction hides differences in location at several scales. [6] From [Quantitative lower bounds for trace reconstruction](https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf): > The two words use complementary signed patterns in their central segments. [7] From [Quantitative lower bounds for trace reconstruction](https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf): > The generating polynomial of a Prouhet--Thue--Morse pattern vanishes to high order at $1$, making its convolution with a broad binomial offset small. [8] From [Uniform quasipolynomial-time trace reconstruction](https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf): > We give a uniform algorithm that reconstructs every binary string from independent deletion traces when its length and rational retention probability are known. [9] From [Uniform quasipolynomial-time trace reconstruction](https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf): > For each fixed retention probability, both the number of traces and the bit complexity are quasipolynomial in the string length. [10] From [Uniform quasipolynomial-time trace reconstruction](https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf): > Reconstruction succeeds with probability at least $2/3$ for each input string. [11] From [Uniform quasipolynomial-time trace reconstruction](https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf): > The resulting tests determine one bit at a time and can be implemented using rational arithmetic. [12] From [Uniform quasipolynomial-time trace reconstruction](https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf): > It enables constructive feasibility tests in place of a search over complete strings. [13] From [A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction](https://github.com/openai/math/blob/main/preprints/A-latest-anchor-induction-with-spectrally-compact-masks-for-worst-case-trace-reconstruction-October-5-2026/paper.pdf): > They concern sample complexity and do not assert an efficient reconstruction algorithm or matching optimality. [14] From [Uniform quasipolynomial-time trace reconstruction](https://github.com/openai/math/blob/main/preprints/Uniform-quasipolynomial-time-trace-reconstruction-October-5-2026/uniform-trace-reconstruction.pdf): > If the deletion probability is at most $n^{-\varepsilon}$ for fixed $\varepsilon>0$, the sample and running-time bounds are polynomial. [15] From [Quantitative lower bounds for trace reconstruction](https://github.com/openai/math/blob/main/preprints/quantitative-lower-bounds-for-trace-reconstruction-September-24-2026/paper.pdf): > 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. ## Other sources - [T. Batu, S. Kannan, S. Khanna and A. McGregor, “Reconstructing Strings from Random Traces”, SODA 2004](https://people.cs.umass.edu/~mcgregor/papers/04-soda.pdf) - [T. Holenstein, M. Mitzenmacher, R. Panigrahy and U. Wieder, “Trace reconstruction with constant deletion probability and related results”, SODA 2008](https://www.eecs.harvard.edu/~michaelm/postscripts/soda2008c.pdf) - [A. De, R. O'Donnell and R. Servedio, “Optimal Mean-Based Algorithms for Trace Reconstruction”, STOC 2017](https://doi.org/10.1145/3055399.3055450) - [F. Nazarov and Y. Peres, “Trace Reconstruction with exp(O(n^{1/3})) Samples”, STOC 2017](https://arxiv.org/abs/1612.03599) - [N. Holden and R. Lyons, “Lower Bounds for Trace Reconstruction”, Annals of Applied Probability (2020)](https://doi.org/10.1214/19-AAP1506) - [Z. Chase, “New lower bounds for trace reconstruction”, Ann. Inst. Henri Poincaré Probab. Stat. (2021)](https://doi.org/10.1214/20-AIHP1089) - [Z. Chase, “Separating words and trace reconstruction”, STOC 2021](https://doi.org/10.1145/3406325.3451118) - [Burudgunte, Valiant and Wang, “Quasipolynomial Trace Reconstruction”, arXiv:2607.04073 (2026)](https://arxiv.org/abs/2607.04073v1) - [openai/math, Lean scope note for family 122 (2026)](https://github.com/openai/math/blob/main/lean/docs/122.md): “The formalization proves superpolynomial sample lower bounds for exact worst-case reconstruction of binary words from independent deletion traces” ## Related - [The metric k -median approximation threshold and recovery](https://closedform.nishachay.tech/e/openai-math-2026-125/) - Theoretical computer science - [Uniform black-box noncommutative identity testing across characteristics](https://closedform.nishachay.tech/e/openai-math-2026-116/) - Theoretical computer science - [Sampling and counting contingency tables with arbitrary margins](https://closedform.nishachay.tech/e/openai-math-2026-115/) - Theoretical computer science - [Approximate counting of common integer polymatroid bases](https://closedform.nishachay.tech/e/openai-math-2026-114/) - Theoretical computer science - [Hardness of coloring three-colorable graphs](https://closedform.nishachay.tech/e/openai-math-2026-106/) - Theoretical computer science - [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 40 results - [Open since the 2000s](https://closedform.nishachay.tech/open-since/2000s/) - Era · 48 results - [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20122%5D%20)