Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

  • Nina Holden

    ETH Zürich, Switzerland
  • Robin Pemantle

    University of Pennsylvania, Philadelphia, USA
  • Yuval Peres

    Microsoft Research, Redmond, USA
  • Alex Zhai

    Stanford University, USA
Subpolynomial trace reconstruction for random strings and arbitrary deletion probability cover

A subscription is required to access this article.

Abstract

The insertion-deletion channel takes as input a bit string , and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover from many independent outputs (called "traces") of the insertion-deletion channel applied to . We show that if is chosen uniformly at random, then traces suffice to reconstruct with high probability. For the deletion channel with deletion probability the earlier upper bound was exp. The case of or the case where insertions are allowed has not been previously analyzed, and therefore the earlier upper bound was as for worst-case strings, i.e., exp. We also show that our reconstruction algorithm runs in time.

A key ingredient in our proof is a delicate two-step alignment procedure where we estimate the location in each trace corresponding to a given bit of . The alignment is done by viewing the strings as random walks and comparing the increments in the walk associated with the input string and the trace, respectively.

Cite this article

Nina Holden, Robin Pemantle, Yuval Peres, Alex Zhai, Subpolynomial trace reconstruction for random strings and arbitrary deletion probability. Math. Stat. Learn. 2 (2019), no. 3/4, pp. 275–309

DOI 10.4171/MSL/16