Trace Reconstruction Revisited
Trace Reconstruction Revisited
复制标题
痕迹重建重温
DOI：
10.1007/978-3-662-44777-2_57
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Sofya Vorotnikova
中科院分区：
文献类型：
--
作者：
A. Mcgregor;Eric Price;Sofya Vorotnikova
迹重建问题是重建长度为n的字符串x，给定m个随机序列，其中每个子序列是通过以概率p独立地删除x的每个字符而生成的。两个自然问题是a）m必须作为n和p的函数有多大，使得重建可能具有高概率，以及B）如何有效地执行这种重建。现有的工作考虑的情况下，当x是随机的，当x是任意的。在本文中，我们将这两种情况的复杂性联系起来;改进Holenstein等人（SODA 2008）在这两种情况下m的充分值上的界限;并对Viswanathan和Swaminathan（SODA 2008），Kannan和McGregor（ISIT 2005）以及Batu等人（SODA 2004）证明的一些结果进行简单得多的分析。特别是，我们的工作意味着第一次多项式的上限（当字母表是polylogn）和超对数下限时，X是随机的，P是常数所需的痕迹的数量。
The trace reconstruction problem is to reconstruct a string x of length n given m random subsequences where each subsequence is generated by deleting each character of x independently with probability p. Two natural questions are a) how large must m be as a function of n and p such that reconstruction is possible with high probability and b) how can this reconstruction be performed efficiently. Existing work considers the case when x is chosen uniformly at random and when x is arbitrary. In this paper, we relate the complexity of both cases; improve bounds by Holenstein et al. (SODA 2008) on the sufficient value of m in both cases; and present a significantly simpler analysis for some of the results proved by Viswanathan and Swaminathan (SODA 2008), Kannan and McGregor (ISIT 2005), and Batu et al. (SODA 2004). In particular, our work implies the first sub-polynomial upper bound (when the alphabet is polylogn) and super-logarithmic lower bound on the number of traces required when x is random and p is constant.