Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem

Ittai Rubinstein

The {\em insertion-deletion channel} takes as input a binary string $x\in \{0,1{\}}^n$, and outputs a string $\tilde{x}$ where some of the bits have been deleted and others inse…