A Uniform Decoder Reconstructs Strings From Randomly Deleted Traces

In trace reconstruction, each bit of an unknown string survives independently with probability p. The surviving bits slide together in their original order, but a trace does not say which input positions they came from. Repeating the deletion process gives independent traces; simply aligning their first bits and taking a majority vote does not reliably recover the original coordinates. The goal is to reconstruct the entire string, which may be any string of the stated length.

The manuscript claims a uniform algorithm: one finite program that takes a known length n of at least 2 and a known rational retention probability p greater than 0 and at most 1. For every binary string of that length, it recovers the string with probability at least two-thirds. At each fixed p, both the number of traces and the computation are quasipolynomial in n. This is an asymptotic guarantee, not a claim of practical speed.^†

The distinction matters because statistics that distinguish candidate strings do not by themselves give an efficient way to find an unknown one. There are 2ⁿ possible strings. The claimed contribution is a route from information in the traces to a bounded decoder, without searching that entire space.

The decoder uses products of bits at selected trace ranks. For example, choose ranks 1 and 3 and multiply the bits found there. The product is zero if either bit is zero; it is also zero if rank 3 does not exist in that trace. Averaging across independent traces estimates an observable denoted T_I, where I is the selected set of ranks.

These statistics can involve ranks separated by large gaps, not only consecutive blocks. Their expected values are polynomials in the original bits with non-negative rational coefficients determined by the deletion channel. The measurements are indexed by positions in the trace; they do not reveal the corresponding input positions.

To avoid enumerating every possible ending of the string, the algorithm represents a proposed prefix through a table of moments for the remaining bits. It writes each bit X as a sign Y = 2X − 1, so Y² = 1. Entries in the table encode expectations such as E[Y₃Y₄]. Requiring the moment matrix to be positive semidefinite imposes a necessary condition: the expected square of every polynomial up to a chosen degree must be nonnegative.

This is a relaxation, not a representation of actual strings. A positive semidefinite moment table need not come from any distribution over possible endings. That extra freedom sharpens the central question: can a false prefix pass the tests by choosing a feasible but unrealizable table?

The manuscript’s separation claim says it cannot. Suppose a proposed prefix agrees with the true string up to some position and then puts the wrong bit there. The moment table and the true string differ at that position by magnitude one. For p below 1, some trace observable of controlled degree must differ from its true value by more than an explicitly exponentially small threshold. The claim applies even to positive moment arrays that do not arise from genuine distributions. The proof must rule out a whole family of false completions, not merely show that two known strings produce different statistics.

The explainer sketches the analytic route without giving the full proof. Exponential damping makes nearby positions more influential. The argument carries a detectable discrepancy to larger distance scales while increasing the number of positions in the statistics. Positivity provides inner products for a chaining argument; Gaussian contour deformation and an interleaving bound help convert products into controlled tuple statistics. Tuple order grows by at most a factor of four per stage. These estimates produce witnesses to separation; the decoder itself does not search for them.

A counting identity links hidden input gaps to observed ranks. In a gap of g positions, each position contributes q = 1 − p if deleted, or p times u if retained and marked by u. The gap therefore contributes (q + pu)ᵍ. Selected endpoint bits contribute their own retention factors. Setting z = q + pu maps the unit disk for u to a disk centered at q with radius p. The proof uses these disks to control the gap parameters together.

Separation explains why a wrong prefix should fail, but an algorithm also needs a correct prefix to pass its feasibility test. The proof establishes this by mixing the true completion with a small amount of independent uniform signs. The uniform signs have identity moment matrix: squared signs give diagonal entries of one, while products of distinct independent signs have mean zero. If the mixing weight is alpha, the resulting matrix is the true matrix weighted by 1 − alpha, plus alpha times the identity. Since the true matrix is positive semidefinite, the mixture has eigenvalues at least alpha, giving it strict slack.

Each observable lies between zero and one, so this mixture changes its expectation by at most alpha. Setting alpha to zeta divided by eight, where zeta is the decoder’s tolerance, keeps the mixture within zeta divided by four of empirical estimates that are within zeta divided by eight of their true values. That is inside the allowed tolerance. This constructs a feasible interior point for the analysis; the decoder does not know the true ending.

The algorithm tests both possible next-bit extensions using exact rational checks. Updates are clipped and rounded to a fixed binary grid, and a fixed iteration cap guarantees termination. When all empirical moments are accurate, the correct extension is feasible and the wrong one is not. Repeating this decision reconstructs every bit. The success guarantee depends on that accuracy event: if the empirical moments are all accurate, the tests support the correct decisions throughout. On bad data, an ambiguous test defaults to appending zero, so the program still halts with an n-bit output.

The sample budget is ⌈exp(CB(n,p))⌉, with C an absolute constant. The scale B and the two stated regimes are:

For q greater than zero, B(n,p) = p⁻¹(log n)X²(1 + log X)⁶, where X = 1 + log n / (1 + log(1/q)); when q is zero, X is defined to be 1. All logarithms are natural. Computation is polynomial in n, the total binary length L of the numerator and denominator of p, and the sample budget. The claimed cap applies to every internal random-bit sequence and every well-formed trace stream whose strings have at most n bits, even if reconstruction fails.

The mathematical contribution is a uniform route from trace moments to prefix feasibility and then to one-bit decisions: wrong relaxed prefixes are excluded, while strict slack lets correct prefixes pass.