论文标题
从单个跟踪中的近似痕量重建
Approximate Trace Reconstruction from a Single Trace
论文作者
论文摘要
The well-known trace reconstruction problem is the problem of inferring an unknown source string $x \in \{0,1\}^n$ from independent "traces", i.e. copies of $x$ that have been corrupted by a $δ$-deletion channel which independently deletes each bit of $x$ with probability $δ$ and concatenates the surviving bits.当前的论文考虑了极端数据限制的制度，其中仅向重建算法提供单个迹线。在此设置中，精确重建当然是不可能的，问题是源字符串$ x $可以大致重建的准确性。 我们对这个问题进行了详细的研究，在最差的情况下（$ x $是任意）和平均案例（$ x $均从$ \ \ \ {0,1 \}^n $均匀地绘制的算法和低删除率制度（$ x $是任意）和平均值（$ x $）的算法和下限。在某些情况下，我们确定的下限与我们提供的计算有效算法相匹配。 我们重点介绍了高删除率制度的结果：粗略地说，他们表明 - 对于最坏情况的痕量重建，可以访问单个跟踪已经非常有用：有效的算法可以执行更准确的重建，给定一个迹线甚至只有几个位，而不是根本没有痕迹。但相反， - 在平均情况下，可以访问单个跟踪是不是很有用：没有算法在计算上有效或以其他方式，可以在一个迹线（$ o（n）$ lits长的情况下，都比没有痕迹的痕迹达到$ o（n）$ lits的准确性明显更高。
The well-known trace reconstruction problem is the problem of inferring an unknown source string $x \in \{0,1\}^n$ from independent "traces", i.e. copies of $x$ that have been corrupted by a $δ$-deletion channel which independently deletes each bit of $x$ with probability $δ$ and concatenates the surviving bits. The current paper considers the extreme data-limited regime in which only a single trace is provided to the reconstruction algorithm. In this setting exact reconstruction is of course impossible, and the question is to what accuracy the source string $x$ can be approximately reconstructed. We give a detailed study of this question, providing algorithms and lower bounds for the high, intermediate, and low deletion rate regimes in both the worst-case ($x$ is arbitrary) and average-case ($x$ is drawn uniformly from $\{0,1\}^n$) models. In several cases the lower bounds we establish are matched by computationally efficient algorithms that we provide. We highlight our results for the high deletion rate regime: roughly speaking, they show that - Having access to a single trace is already quite useful for worst-case trace reconstruction: an efficient algorithm can perform much more accurate reconstruction, given one trace that is even only a few bits long, than it could given no traces at all. But in contrast, - in the average-case setting, having access to a single trace is provably not very useful: no algorithm, computationally efficient or otherwise, can achieve significantly higher accuracy given one trace that is $o(n)$ bits long than it could with no traces.
