Quantitative trace-reconstruction bounds with a uniform decoder

1 · The essentials

Imagine trying to recover a sequence of zeros and ones from copies in which some entries have been randomly erased. Each copy preserves the order of the entries that remain, but leaves you to work out what is missing. This family of manuscripts studies how many independent copies are needed and how much computation recovery takes. For any fixed erasure probability strictly between zero and one, the lower-bound manuscript shows that no fixed power of the sequence length can bound the number of copies needed for every sequence. The main manuscript gives a single recovery procedure whose copy count and computation grow more slowly than an exponential in the length, though its bounds are not polynomial for fixed erasure probabilities. It assumes that the length and the rational probability of keeping an entry are known, and succeeds with probability at least two-thirds for each sequence. If the erasure probability decreases sufficiently quickly with length, its bounds become polynomial. The main result has a Lean formalization, although the supplied description does not specify exactly which claims it covers.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine receiving several copies of a numbered checklist, with random items missing from each copy and the surviving items still in order. Comparing the copies can help recover the original, but this image leaves out the precise random-erasure model and the difficulty of distinguishing very similar originals.

Why it matters

The results separate a shortage of information from a shortage of computing power: the lower bound applies even when computation is unrestricted. They also distinguish a fixed erasure rate from one that becomes small as the sequence grows. Together, the manuscripts give quantitative limits on recovery and a uniform procedure with explicit resource bounds, without claiming that the upper and lower bounds match.

2 · Going further

The problem is exact worst-case trace reconstruction: recover an arbitrary length- $n$ binary string from independent deletion traces, with the length and retention probability known. Write $q$ for deletion probability, so retention probability is $1 - q$ . The main manuscript gives a uniform algorithm for known rational retention probabilities, with success probability at least $2/3$ for every input string. For each fixed retention probability, its sample count and bit complexity are quasipolynomial; more generally, it gives an explicit sample bound across rational retention probabilities and running time polynomial in the sample budget and binary input length.

The sample-bound companion gives a quasipolynomial budget whose logarithm is $O ((lo g n)^{3} (1 + lo g lo g (2 n))^{6})$ for each fixed retention probability. It covers both binary strings and general symbols observed exactly, but does not assert an efficient reconstruction algorithm. Its title identifies a “latest-anchor induction with spectrally compact masks”; the supplied abstracts do not explain that mechanism or the main decoder’s argument, so a more detailed account of the proof strategy is not available from this source. Both upper-bound manuscripts give polynomial sample bounds when $q \leq n^{- ε}$ for fixed $ε > 0$ , and the main manuscript also gives polynomial running-time bounds in that regime.

The lower-bound companion shows in the manuscript that every fixed $q \in (0, 1)$ requires $n^{Ω (l o g l o g n)}$ samples for exact worst-case reconstruction, even with unrestricted computation and any fixed positive success probability. More generally, when $q^{3} lo g n \to \infty$ , it gives the lower bound $n^{c l o g (q^{3} l o g n)}$ for every fixed $0 < c < 1/ (4 lo g 2)$ , with all logarithms natural. This answers the polynomial-sample question negatively for fixed deletion probabilities. The companions therefore address distinct aspects of the same problem: sample sufficiency, a uniform computational decoder, and necessary sample counts.

Useful notions

Binary strings and their length
Independent random observations
Deletion and retention probabilities
Polynomial and quasipolynomial growth
Worst-case resource bounds

What was known before / what is new

Before

The source identifies whether polynomially many samples suffice for binary trace reconstruction as a question addressed by this family. It calls the sample bound in the second manuscript improved, but supplies no earlier quantitative bound or historical attribution for comparison.

New

The main manuscript supplies a uniform decoder with quasipolynomial sample and bit-complexity bounds for known fixed rational retention probabilities, and an explicit sample bound uniform over rational retention probabilities. The sample-bound companion gives a more specific quantitative budget and also covers general symbols observed exactly. The lower-bound companion shows in the manuscript that polynomially many samples cannot suffice in the worst case at any fixed deletion probability strictly between zero and one. In the sufficiently small deletion regime, the main decoder instead has polynomial sample and running-time bounds.

Limits and assumptions

These are worst-case exact-recovery results from independent deletion traces, not guarantees of certain success from every observed collection of traces. The main decoder requires known length and known rational retention probability and guarantees success probability at least 2/3 for each input string. Its polynomial regime assumes q ≤ n^(−ε) for fixed ε > 0; the fixed-rate lower bound instead assumes a deletion probability in (0,1) that does not vary with length. The second manuscript addresses samples only and does not claim computational efficiency or matching optimality. The main result has a Lean formalization, but the supplied source does not identify its precise coverage, so formal verification should not be extended to all companion claims. Matching upper and lower bounds are not established in the supplied account.

Mini glossary

Deletion trace: An observation formed by randomly deleting entries of a string while retaining the order of the surviving entries.
Worst-case reconstruction: Recovery with a stated success guarantee for every input string, rather than only for selected or typical strings.
Sample complexity: The number of independent traces needed for a reconstruction guarantee.
Quasipolynomial bound: A resource bound of the form exp((log n) raised to a fixed power), up to constants in the exponent.
Uniform decoder: A single reconstruction algorithm that takes the known length and rational retention probability as inputs.
Bit complexity: Computational cost measured in operations on the binary representations of data and parameters.

Keywords : Trace reconstruction · Sample complexity · Uniform decoding

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

At every fixed deletion probability in $(0, 1)$ , reconstructing an arbitrary length-n binary string requires $n^{Ω (l o g l o g 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^{- ε}$ for fixed ε > 0, both bounds become polynomial in the input and parameter encoding.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/122.md

Manuscripts in this family

★

Uniform quasipolynomial-time trace reconstruction

05/10/2026

To be verified

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^{- ε}$ for fixed ε > 0, the sample and running-time bounds are polynomial. Reconstruction succeeds with probability at least 2/3 for each input string.

PDF GitHub folder

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

05/10/2026

To be verified

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 ((lo g n)^{3} (1 + lo g lo g (2 n))^{6})$ . If the deletion probability is at most $n^{- ε}$ 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.

PDF GitHub folder

Quantitative lower bounds for trace reconstruction

24/09/2026

To be verified

Exact worst-case reconstruction of a binary word from independent deletion traces requires $n^{Ω (l o g l o g 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} lo g n \to \infty$ , we prove a lower bound of $n^{c l o g (q^{3} l o g n)}$ samples for every fixed $0 < c < 1/ (4 lo g 2)$ . Here q is the known deletion probability, and all logarithms are natural.

PDF GitHub folder