Optimal mean-based algorithms for trace reconstruction

In the (deletion-channel) trace reconstruction problem, there is an unknown n -bit source string x . An algorithm is given access to independent traces of x , where a trace is formed by deleting each bit of x independently with probability δ. The goal of the algorithm is to recover x exactly (with high probability), while minimizing samples (number of traces) and running time. Previously, the best known algorithm for the trace reconstruction problem was due to Holenstein et al. [SODA 2008]; it uses exp( O ( n 1/2 )) samples and running time for any fixed 0 1/2, the presence of insertions can actually help with trace reconstruction.

Authors

• Anindya De
• Ryan O'Donnell
• Rocco A. Servedio

Keywords

• Littlewood polynomials
• Trace reconstruction
• deletion channel