Speaker
Description
Ittai Rubinstein
Abstract: The {\em insertion-deletion channel} takes as input a binary string $x \in\{0, 1\}^n$, and outputs a string $\widetilde{x}$ where some of the bits have been deleted and others inserted independently at random.
In the {\em trace reconstruction problem}, one is given many outputs (called {\em traces}) of the insertion-deletion channel applied to the same input message $x$, and is asked to recover the input message.
De, O'Donnell and Servedio (STOC 2017), and Nazarov and Peres (STOC 2017) showed that any string $x$ can be reconstructed from $\exp(O(n^{1/3}))$ traces.
Holden, Pemantle, Peres and Zhai (COLT 2018) adapt the techniques used to prove this upper bound, to an algorithm for the average-case trace reconstruction with a sample complexity of $\exp(O(\log^{1/3} n))$.
However, it is not clear how to apply their techniques more generally and in particular for the recent worst-case upper bound of $\exp(\widetilde{O}(n^{1/5}))$ shown by Chase(STOC 2021) for the deletion channel.
We prove a general reduction from the average-case to smaller instances of a problem similar to worst-case.
Using this reduction and a generalization of Chase's bound, we construct an improved average-case algorithm with a sample complexity of $\exp(\widetilde{O}(\log^{1/5} n))$.
Additionally, we show that Chase's upper-bound holds for the insertion-deletion channel as well.