插入和删除时的有效平均案例群体恢复
原创
作者：Frank Ban,Xi Chen,Rocco A. Servedio,Sandip Sinha
摘要：最近的一些研究考虑了\ emph {trace重构问题}，其中未知源字符串x∈{0,1} n通过概率信道传输，该信道可以随机删除坐标或插入随机位，从而产生\ emph {追踪x。目标是从x的独立轨迹重建原始字符串~x。虽然最坏情况字符串已知的最佳算法使用exp（O（n1 / 3））trace \ cite {DOS17，NazarovPeres17}，但已知高效算法\ cite {PZ17，HPP18} \ emph {average-case}版本，其中x是均匀随机的。我们考虑这种平均情况跟踪重建问题的概括，我们将其称为\ emph {存在插入和删除时的平均情况人口恢复}。在这个问题中，在未知的源串x1，...，xs∈{0,1} n上存在未知的分布D，并且通过从D绘制一些xi并返回xi的独立轨迹来独立地生成每个样本。
在\ cite {PZ17}和\ cite {HPP18}的基础上，我们为此问题提供了一种有效的算法。对于任何支撑尺寸s≤exp（Θ（n1 / 3）），对于每个分布的所有s元素支撑集{x1，...，xs}⊂{0,1} n的1-o（1）分数在{x1，...，xs}上支持D，我们的算法以高概率有效地恢复D到总变差距离ε，从而获得从D独立绘制的独立轨迹。算法在时间上运行poly（n，s，1 / ε）及其样本复杂度为poly（s，1 /ε，exp（log1 / 3n））。这种对支持大小s的多项式依赖与\ emph {最坏情况}版本形成鲜明对比（当x1，...，xs可能是{0,1} n中的任何字符串时），其中样本复杂度最高有效的已知算法\ cite {BCFSS19}在s中是双指数的。
原文标题：Efficient average-case population recovery in the presence of insertions and deletions
原文摘要：
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。