论文标题
对于痕量重建问题的平均案例降低（移动）最差的案例减少
Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem
论文作者
论文摘要
{\ em intertion-deletion channel}将作为输入为二进制字符串$ x \ in \ {0，1 \}^n $，并输出一个字符串$ \ widetilde {x} $，其中某些位已被删除，而另一些位则随机插入。在{\ em跟踪重建问题}中，在同一输入消息$ x $上给出了许多输出（称为{\ em Traces}）的许多输出（称为{\ em Traces}），并要求恢复输入消息。 Nazarov and Peres（Stoc 2017）以及DE，O'Donnell and Serveio（Stoc 2017）表明，可以从$ \ exp（o（n^{1/3}））$ traces traces重建任何字符串$ x $。 Holden，Pemantle，Peres和Zhai（Colt 2018）将用于证明这种上限的技术适应了平均案例痕量重建的算法，其样品复杂性为$ \ exp（O（\ log^{1/3} n）））$。但是，尚不清楚如何更普遍地应用其技术，尤其是对于最近的$ \ exp（\ widetilde {o}（n^{1/5}）$的最差案例上限）$ chase（stoc 2021）用于删除范围。 我们证明，从平均情况到类似于最坏情况的问题的较小实例的总体降低。使用这种降低和对Chase的界限的概括，我们构建了一个改进的平均案例算法，其样品复杂性为$ \ exp（\ widetilde {o}（\ log^{1/5} n））$。此外，我们还表明，Chase的上限也适用于插入消耗通道。
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 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(\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.
