The Quasi-probability Method and Applications for Trace Reconstruction

Ittai Rubinstein

In the trace reconstruction problem, one attempts to reconstruct a fixed but unknown string $x$ of length $n$ from a given number of traces $\tilde{x}$ drawn iid from the applicati…