论文标题
平滑复杂度模型中的多项式时间重建
Polynomial-time trace reconstruction in the smoothed complexity model
论文作者
论文摘要
在\ emph {跟踪重建问题}中，通过概率\ emph {删除通道}发送了一个未知的源字符串$ x \ in \ {0,1 \}^n $，该份数独立地删除了每个位，该位以概率$δ$和串联的范围，并产生\ emph $ x $ x $ x $ x $。问题是重建$ x $给定的独立痕迹。近年来，这个问题在最差的环境中引起了很多关注，$ x $可能是$ \ {0,1 \}^n $ \ cite {dos17，nazarovperes17，hhp18，hhp18，hl18，hl18，chase19}的$ x $ $ x $ a $ n o $ n y y y n $ n y的$ n y $ \ cite {pereszhai17，hpp18，hl18，chase19}。 本文研究在\ emph {平滑的分析}设置中进行追踪重建，其中``word-case''字符串$ x^{\ worst} $是从$ \ {0,1 \}^n $任意选择的概率$σ$。问题是从中重建$ \ bx $。 我们的主要结果是一种算法，对于任何恒定的扰动速率$ 0 <σ<1 $和任何常数删除率$ 0 <Δ<1 $，使用$ \ poly（poly \ poly（poly \ poly（n）$）$运行时间和迹线，并且在重建字符串$ \ bx $的重建方面具有很高的可能性。这与问题的最坏版本相反，该版本$ \ text {exp}（o（n^{1/3}））$是最著名的时间和样本复杂性\ cite \ cite {dos17，nazarovperes17}。 我们的方法是基于从其简短子字的多键中重建$ \ bx $，并且与以前最差的问题或平均案例版本的算法完全不同。我们工作的核心是一个新的$ \ poly（n）$ - 时间步骤，用于重建所有$ o（\ log n）$ - 长度子字的多源 - 任何源字符串$ x \ in \ in \ {0,1 \}^n $的长度子字。
In the \emph{trace reconstruction problem}, an unknown source string $x \in \{0,1\}^n$ is sent through a probabilistic \emph{deletion channel} which independently deletes each bit with probability $δ$ and concatenates the surviving bits, yielding a \emph{trace} of $x$. The problem is to reconstruct $x$ given independent traces. This problem has received much attention in recent years both in the worst-case setting where $x$ may be an arbitrary string in $\{0,1\}^n$ \cite{DOS17,NazarovPeres17,HHP18,HL18,Chase19} and in the average-case setting where $x$ is drawn uniformly at random from $\{0,1\}^n$ \cite{PeresZhai17,HPP18,HL18,Chase19}. This paper studies trace reconstruction in the \emph{smoothed analysis} setting, in which a ``worst-case'' string $x^{\worst}$ is chosen arbitrarily from $\{0,1\}^n$, and then a perturbed version $\bx$ of $x^{\worst}$ is formed by independently replacing each coordinate by a uniform random bit with probability $σ$. The problem is to reconstruct $\bx$ given independent traces from it. Our main result is an algorithm which, for any constant perturbation rate $0<σ< 1$ and any constant deletion rate $0 < δ< 1$, uses $\poly(n)$ running time and traces and succeeds with high probability in reconstructing the string $\bx$. This stands in contrast with the worst-case version of the problem, for which $\text{exp}(O(n^{1/3}))$ is the best known time and sample complexity \cite{DOS17,NazarovPeres17}. Our approach is based on reconstructing $\bx$ from the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new $\poly(n)$-time procedure for reconstructing the multiset of all $O(\log n)$-length subwords of any source string $x\in \{0,1\}^n$ given access to traces of $x$.
