A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities

Joey Rivkin, Gregory Valiant, Paul Valiant

We introduce the following natural generalization of trace reconstruction, parameterized by a deletion probability $\delta \in (0,1)$ and length $n$: There is a length $n$ string of prob…