Tree trace reconstruction using subtraces
Tree trace reconstruction using subtraces
复制标题
使用子迹重建树迹
DOI：
10.1017/jpr.2022.81
复制
发表时间：
2023
影响因子：
1
通讯作者：
Rácz, Miklós Z.
中科院分区：
文献类型：
--
作者：
Brailovskaya, Tatiana;Rácz, Miklós Z.
树迹重构的目的是学习树的二进制节点标签，给定树的独立样本通过适当定义的删除通道。在最近的工作中，Davies，Rácz和Rashtchian [10]使用组合方法证明样本足以以高概率重建具有n个节点的完整k叉树。我们提供了另一种证明这一结果，这使我们能够推广到更广泛的一类树拓扑结构和删除模型。在我们的证明中，我们引入了一个subtrace的概念，这使我们能够连接和推广最近的平均为基础的复杂的分析算法的字符串跟踪重建。
Tree trace reconstruction aims to learn the binary node labels of a tree, given independent samples of the tree passed through an appropriately defined deletion channel. In recent work, Davies, Rácz, and Rashtchian [10] used combinatorial methods to show that samples suffice to reconstruct a complete k-ary tree with n nodes with high probability. We provide an alternative proof of this result, which allows us to generalize it to a broader class of tree topologies and deletion models. In our proofs we introduce the notion of a subtrace, which enables us to connect with and generalize recent mean-based complex analytic algorithms for string trace reconstruction.
登录
查看更多内容
从随机痕迹重建字符串
影响因子：
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
具有不同删除概率的迹线重建
DOI：
10.1137/1.9781611975062.6
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Lisa Hartung;N. Holden;Y. Peres
通讯作者：
Y. Peres
平滑复杂度模型中的多项式时间迹重建
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