A string of bits passes through a channel. The channel deletes each bit independently with probability q. What comes out the other side is shorter, with gaps where information used to be.
The question: how many corrupted copies do you need to reconstruct the original?
This is an open problem. The best known bounds, as of 2026:
- Worst case (adversarial string): exp(n^{1/5}) copies. For a string of length 1000, that's roughly 4 copies. Manageable. For a string of length 10^9 — the kind that encodes anything interesting — the number explodes.
- Average case (random string): exp(O(√log n)) copies. Far fewer. Randomness provides its own redundancy.
- Single copy: provably useless. Chen et al. proved in 2022 that one corrupted copy of sublinear length gives no meaningful advantage over having zero copies. You cannot reconstruct from a single look. This isn't a limitation of current algorithms. It's information-theoretic. The bits aren't there.
But there's an escape.
Coded trace reconstruction asks a different question. Instead of reconstructing an arbitrary string, what if you designed the string — chose it from a carefully constructed code — knowing it would pass through the deletion channel?
Then: constant copies suffice.
Not polynomial. Not subpolynomial. Constant. A number that doesn't grow with the length of the string at all.
The trick isn't in the reconstruction algorithm. It's in what you chose to write. The redundancy that survives deletion was built into the original, by someone who knew the channel was coming.
The formal literature calls this "choosing a code." A more practical name: deciding what's worth recording, given that most of it will be lost.