Approximate trace reconstruction of random strings from a constant number of traces
Approximate trace reconstruction of random strings from a constant number of traces
复制标题
从恒定数量的迹线中近似重建随机字符串
DOI：
10.1109/tit.2021.3066010
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
Y. Peres
中科院分区：
文献类型：
--
作者：
Zachary Chase;Y. Peres
在跟踪重建问题中，目标是通过通过删除频道通过$ x $获得的多个轨迹重建一个未知字符串的长度$ n $的$ x $。在放松的问题$近似值$ trace重建中，目标是重建$ \ widehat {x} $ $ x $的$ x $，该$ x $（在$ \ epsilon n $之内）至$ x $编辑距离。我们表明，对于大多数字符串$ x $，仅使用恒定数量的跟踪，这是可能的。至关重要的是，这种常数不会随$ n $而增长，仅取决于删除概率和$ \ epsilon $。
In the trace reconstruction problem, the goal is to reconstruct an unknown string $x$ of length $n$ from multiple traces obtained by passing $x$ through the deletion channel. In the relaxed problem of $approximate$ trace reconstruction, the goal is to reconstruct an approximation $\widehat{x}$ of $x$ which is close (within $\epsilon n$) to $x$ in edit distance. We show that for most strings $x$, this is possible with high probability using only a constant number of traces. Crucially, this constant does not grow with $n$, and only depends on the deletion probability and $\epsilon$.
登录
查看更多内容
有界编辑距离的轨迹重建
DOI：
--
发表时间：
2021
期刊：
International Symposium on Information Theory and its Applications
影响因子：
--
作者：
Sima, J.;Bruck, J.
通讯作者：
Bruck, J.
迹线重建：广义化和参数化
影响因子：
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
平滑复杂度模型中的多项式时间迹重建
DOI：
10.1137/1.9781611976465.5
发表时间：
2021
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Chen, Xi;De, Anindya;Lee, Chin Ho;Servedio, Rocco A.;Sinha, Sandip
通讯作者：
Sinha, Sandip
几乎任何复制插入通道上基于均值的跟踪重建
DOI：
10.1109/isit45174.2021.9518161
发表时间：
2021
期刊：
2021 IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Cheraghchi, Mahdi;Downs, Joseph;Ribeiro, Joao;Veliche, Alexandra
通讯作者：
Veliche, Alexandra