Before revision:  The best known algorithms for trace reconstruction require \exp O(n^{1/3)} samples. For population recovery under the deletion channel , Ban et . al. provided an algorithm that could learn \ell-sparse distributions over strings using \exp  \big( n^{1/2} \cdot (\log n)^{O(\ell)}  \big) samples.
After revision:  The best known algorithms for trace reconstruction require \exp O(n^{1/3)} under the deletion channel , Ban et . al. provided an algorithm that could learn \ell-sparse distributions over strings using \exp  \big( n^{1/2} \cdot (\log n)^{O(\ell)}  \big) samples.