Average-case reconstruction for the deletion channel

Seminar | October 25 | 3:10-4 p.m. | 1011 Evans Hall

 Alex Zhai, Stanford University

 Department of Statistics

The deletion channel takes as input a bit string $\mathbf{x} \in
\{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 $\mathbf{x}$ from many independent outputs
(called ``traces'') of the deletion channel applied to $\mathbf{x}$.

When the input is drawn uniformly at random, we will explain how to
recover random inputs in $e^{O(\sqrt{\log n})}$ traces when $q <
1/2$. This improves the bound of
Holenstein-Mitzenmacher-Panigrahy-Wieder '08, who showed that
$n^{O(1)}$ traces suffice 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 et al.; and 3) complex analysis techniques from
recent work of Nazarov-Peres '16 and De-O'Donnell-Servedio
'16. Joint work with Yuval Peres.