OAI.TraceReconstruction.superpolynomial_one_trace

The theorem states that, for every deletion probability q strictly between 0 and 1 and every real exponent C>0, the quantity n^C · minTraceTV(n,q) tends to 0 as n tends to infinity through the natural numbers. Here, for a binary word x of length n, a trace is obtained by an independent mask that deletes each bit with probability q and retains it with probability 1−q, the observer seeing only the resulting list of retained bits. traceTV(q,x,y) is the total variation distance, one half the sum of absolute differences of probabilities, between the trace distributions of two words x and y over the finite space of all Boolean lists of length at most n. minTraceTV(n,q) is the infimum of traceTV(q,x,y) over all pairs of distinct words x≠y of length n. Thus the closest pair of distinct words has single-trace distance that decays faster than every polynomial in 1/n. The statement is admitted without proof in the source.