Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem
share
The insertion-deletion channel takes as input a binary string x ∈{0, 1}^n, and outputs a string x where some of the bits have been deleted and others inserted independently at random. In the trace reconstruction problem, one is given many outputs (called traces) of the insertion-deletion channel on the same input message x, and asked to recover the input message. Nazarov and Peres (STOC 2017), and De, O'Donnell and Servedio (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(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(O(log^1/5 n)). Additionally, we show that Chase's upper-bound holds for the insertion-deletion channel as well.
READ FULL TEXT