Trace reconstruction with constant deletion probability and related results
Trace reconstruction with constant deletion probability and related results
复制标题
恒定删除概率的迹线重建及相关结果
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Udi Wieder
中科院分区：
文献类型：
--
作者：
Thomas Holenstein;M. Mitzenmacher;R. Panigrahy;Udi Wieder
对于迹重建问题，我们给出了几个新的结果。在此设置中，二进制串产生轨迹集合，其中每个轨迹是通过以固定概率Δ独立删除每个位来独立获得的。因此，每个轨迹由原始序列的随机子序列组成。给定这些痕迹，我们希望以很高的概率重建原始字符串。问题是重建需要多少轨迹，重建的效率有多高。
我们的初步结果是，对于一些万能常数γ和长度为n的均匀选择的弦，对于任何Δ和lt；γ，在Poly(N)时间内用Poly(N)迹可以高概率地重建。我们还得到了这样的算法：对于任何√<；1，甚至对于最坏情况的字符串，都需要大量的迹指数in‘(Δn)，并且基于迹的汇总统计，我们得到了更简单的算法类的下界结果。
We provide several new results for the trace reconstruction problem. In this setting, a binary string yields a collection of traces, where each trace is independently obtained by independently deleting each bit with a fixed probability Δ. Each trace therefore consists of a random subsequence of the original sequence. Given the traces, we wish to reconstruct the original string with high probability. The questions are how many traces are necessary for reconstruction, and how efficiently can the reconstruction be performed.
Our primary result is that for some universal constant γ and uniformly chosen strings of length n, for any Δ < γ reconstruction is possible with poly(n) traces in poly(n) time with high probability. We also obtain algorithms that require a number of traces exponential in Õ (√n) for any Δ < 1 even for worst case strings, and we derive lower bound results for simpler classes of algorithms based on summary statistics from the traces.