Polynomial-time trace reconstruction in the smoothed complexity model
Polynomial-time trace reconstruction in the smoothed complexity model
复制标题
平滑复杂度模型中的多项式时间迹重建
DOI：
10.1137/1.9781611976465.5
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Sinha, Sandip
中科院分区：
文献类型：
--
作者：
Chen, Xi;De, Anindya;Lee, Chin Ho;Servedio, Rocco A.;Sinha, Sandip
在踪迹重建问题中，未知源串∈{0，1}通过概率删除通道发送，该通道以概率δ独立地删除每个比特，并将幸存的比特连接起来，产生ataceofx。问题是如何重建给定的独立痕迹。最近几年，无论是在最坏情况下可以是{0，1}n[DOS19，Np17，HHP18，HL20，Cha21a，Cha21b]中的任意字符串，还是在平均情况下，从{0，1}n[PZ17，HPP18，HL20，Cha21a，Cha21b]中随机抽取任意一串，都引起了人们的极大关注。本文研究了混合分析环境下的迹重建问题，在这种情况下，从{0，1}n中任意选择一串，然后用概率σ独立地用均匀随机位替换每个坐标所形成的xwors的扰动版本x。问题是在给定独立迹的情况下重构x。我们的主要结果是一个算法，对于任何恒定的扰动速率0<；σ<；1和任何恒定的删除率0<；δ<；1，使用Poly(N)的运行时间，并且跟踪并以很高的概率成功重构字符串x。这与问题的最坏情况版本形成对比，后者具有最好的已知时间和样本复杂性[Cha21b]。我们的方法基于从其短子词的多个集合重构x，并且与以前的算法非常不同，无论是最坏情况还是平均情况。我们工作的核心是一个新的多(N)时间过程，用于重建任意源字符串∈{0，1}n的同源(Logn)长度子字的多集。
In thetrace reconstruction problem, an unknown source stringx∈ {0, 1}nis sent through a probabilisticdeletion channelwhich independently deletes each bit with probabilityδand concatenates the surviving bits, yielding atraceofx. The problem is to reconstructxgiven independent traces. This problem has received much attention in recent years both in the worst-case setting wherexmay be an arbitrary string in {0, 1}n[DOS19, NP17, HHP18, HL20, Cha21a, Cha21b] and in the average-case setting wherexis drawn uniformly at random from {0, 1}n[PZ17, HPP18, HL20, Cha21a, Cha21b].This paper studies trace reconstruction in thesmoothed analysissetting, in which a “worst-case” stringxworstis chosen arbitrarily from {0, 1}n, and then a perturbed version x ofxworstis formed by independently replacing each coordinate by a uniform random bit with probabilityσ. The problem is to reconstruct x given independent traces from it.Our main result is an algorithm which, for any constant perturbation rate 0 <σ< 1 and any constant deletion rate 0 <δ< 1, uses poly(n) running time and traces and succeeds with high probability in reconstructing the string x. This stands in contrast with the worst-case version of the problem, for whichis the best known time and sample complexity [Cha21b].Our approach is based on reconstructing x from the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly(n)-time procedure for reconstructing the multiset of allO(logn)-length subwords of any source stringx∈ {0, 1}ngiven access to traces ofx.
登录
查看更多内容
删除通道的平均情况重建：次多项式多迹就足够了
DOI：
--
发表时间：
2017
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Y. Peres;Alex Zhai
通讯作者：
Alex Zhai
DOI：
10.1007/978-3-662-44777-2_57
发表时间：
2014
期刊：
Annales de l'Institut Henri Poincaré, Probabilités et Statistiques
影响因子：
--
作者：
A. Mcgregor;Eric Price;Sofya Vorotnikova
通讯作者：
Sofya Vorotnikova
从随机痕迹重建字符串
影响因子：
1.5
作者：
Tugkan Batu;Sampath Kannan;S. Khanna;A. Mcgregor
通讯作者：
A. Mcgregor
迹线重建：广义化和参数化
影响因子：
2.5
作者：
Krishnamurthy, Akshay;Mazumdar, Arya;McGregor, Andrew;Pal, Soumyabrata
通讯作者：
Pal, Soumyabrata
DOI：
10.1214/19-aap1506
发表时间：
2020
期刊：
The Annals of Applied Probability
影响因子：
--
作者：
Holden, Nina;Lyons, Russell
通讯作者：
Lyons, Russell