Average-case reconstruction for the deletion channel: subpolynomially many traces suffice

arXiv1708.00854MaRDI QIDQ6289705FDOQ6289705

Authors: Yuval Peres, Alex Zhai 

Publication date: 1 August 2017

Abstract: The deletion channel takes as input a bit string $mathbfxin{0,1}^n$, and deletes each bit independently with probability $q$, yielding a shorter string. The trace reconstruction problem is to recover an unknown string $mathbfx$ from many independent outputs (called "traces") of the deletion channel applied to $mathbfx$. We show that if $mathbfx$ is drawn uniformly at random and $q<1/2$, then $e^{O(lo{g}^{1/2}n)}$ traces suffice to reconstruct $mathbfx$ with high probability. The previous best bound, established in 2008 by Holenstein-Mitzenmacher-Panigrahy-Wieder, uses $n^{O(1)}$ traces and only applies for $q$ less than a smaller threshold (it seems that $q<0.07$ is needed). Our algorithm combines several ideas: 1) an alignment scheme for "greedily" fitting the output of the deletion channel as a subsequence of the input; 2) a version of the idea of "anchoring" used by Holenstein-Mitzenmacher-Panigrahy-Wieder; and 3) complex analysis techniques from recent work of Nazarov-Peres and De-O'Donnell-Servedio.

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10)

This page was built for publication: Average-case reconstruction for the deletion channel: subpolynomially many traces suffice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6289705)