Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
The insertion-deletion channel takes as input a bit string \mathbf x \in \{0,1\}^{n} , and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover \mathbf x from many independent outputs (called "traces") of the insertion-deletion channel applied to \mathbf …