RECONSTRUCTING TREES FROM TRACES

• 成果类型: Article
• 署名作者: Davies, Sami; Racz, Miklos Z.; Rashtchian, Cyrus
• 署名单位: University of Washington; University of Washington Seattle; Princeton University; University of California System; University of California San Diego
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/21-AAP1662
• 发表日期: 2021
• 页码: 2772-2810
• 关键词: information-storage; algorithms; SEQUENCES; distance

摘要

We study the problem of learning a node-labeled tree given independent traces from an appropriately defined deletion channel. This problem, tree trace reconstruction, generalizes string trace reconstruction, which corresponds to the tree being a path. For many classes of trees, including complete trees and spiders, we provide algorithms that reconstruct the labels using only a polynomial number of traces. This exhibits a stark contrast to known results on string trace reconstruction, which require exponentially many traces, and where a central open problem is to determine whether a polynomial number of traces suffice. Our techniques combine novel combinatorial and complex analytic methods.