The Quasi-probability Method and Applications for Trace Reconstruction
Ittai Rubinstein · Society for Industrial and Applied Mathematics eBooks · 2025
In the trace reconstruction problem, one attempts to reconstruct a fixed but unknown string x of length n from a given number of traces x̃ drawn iid from the application of a noisy process (such as the deletion channel) to x. The best known algorithm for the trace reconstruction from the deletion channel is due to Chase, and recovers the input string whp given exp (Õ (n1/5)) traces [Cha21b].