Average-case reconstruction for the deletion channel: subpolynomially many traces suffice

Yuval Peres, Alex Zhai

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 reconstru…