论文标题
低缺失率制度中的多项式时间痕量重建
Polynomial-time trace reconstruction in the low deletion rate regime
论文作者
论文摘要
在\ emph {跟踪重建问题}中，一个未知的源字符串$ x \ in \ {0,1 \}^n $是通过概率\ emph {删除通道}传输的，它独立地删除了每一点，它以固定的概率$δ$和固定的位置，并在$Δ$中固定，并导致$ phit $ phit $ phit $} $} cyphemph = emph = emph {问题是重建$ x $，可以访问独立痕迹。 任意（最坏情况）字符串的痕量重建是一个具有挑战性的问题，当前的Poly $（n）$ - 时间算法是Batu等人的2004年算法。 \ cite {bkkm04}。该算法可以重建一个任意的源字符串$ x \ in \ {0,1 \}^n $ in poly $（n）$ in in Poly $（n）$ time，前提是删除速率$δ$满足$δ\ leq n^{ - （1/2 + \ varepsilon）} $ for Some $ \ varepsilon> varepsilon> 0 $ 0 $ 0 $ 0。 在这项工作中，我们通过给出poly $（n）$ - 时间算法的\ cit {bkkm04}的结果进行改进。我们的算法是通过交替基于对齐的过程来起作用的，我们证明了该过程有效地重建了源字符串的一部分，这些过程不是“高度重复”的，并有效地确定了源字符串高度重复的子字的长度。
In the \emph{trace reconstruction problem}, an unknown source string $x \in \{0,1\}^n$ is transmitted through a probabilistic \emph{deletion channel} which independently deletes each bit with some fixed probability $δ$ and concatenates the surviving bits, resulting in a \emph{trace} of $x$. The problem is to reconstruct $x$ given access to independent traces. Trace reconstruction of arbitrary (worst-case) strings is a challenging problem, with the current state of the art for poly$(n)$-time algorithms being the 2004 algorithm of Batu et al. \cite{BKKM04}. This algorithm can reconstruct an arbitrary source string $x \in \{0,1\}^n$ in poly$(n)$ time provided that the deletion rate $δ$ satisfies $δ\leq n^{-(1/2 + \varepsilon)}$ for some $\varepsilon > 0$. In this work we improve on the result of \cite{BKKM04} by giving a poly$(n)$-time algorithm for trace reconstruction for any deletion rate $δ\leq n^{-(1/3 + \varepsilon)}$. Our algorithm works by alternating an alignment-based procedure, which we show effectively reconstructs portions of the source string that are not "highly repetitive", with a novel procedure that efficiently determines the length of highly repetitive subwords of the source string.
