Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice
Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice
复制标题
删除通道的平均情况重建：次多项式多迹就足够了
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Alex Zhai
中科院分区：
文献类型：
--
作者：
Y. Peres;Alex Zhai
删除通道将比特串x {0，1}^n作为输入，并以概率q独立地删除每个比特，从而产生较短的串。迹重建问题是从应用于x的删除通道的许多独立输出（称为迹）中恢复未知串x。我们证明了如果x是随机均匀绘制的，并且q
The deletion channel takes as input a bit string x ∊ {0,1}^n, and deletes each bit independently with probability q, yielding a shorter string. The trace reconstruction problem is to recover an unknown string x ∊ from many independent outputs (called traces) of the deletion channel applied to x.We show that if x is drawn uniformly at random and q