# 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

## Abstract

The insertion-deletion channel takes as input a bit string $x∈{0,1}_{n}$, and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover $x$ from many independent outputs (called "traces") of the insertion-deletion channel applied to $x$. We show that if $x$ is chosen uniformly at random, then $(O(log_{1/3}n))$ traces suffice to reconstruct $x$ with high probability. For the deletion channel with deletion probability $q<1/2$ the earlier upper bound was exp$(O(log_{1/2}n))$. The case of $q≥1/2$ 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$(O(n_{1/3}))$. We also show that our reconstruction algorithm runs in $n_{1+o(1)}$ 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 $x$. 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