Reconstructing trees from traces
Sami Daviesa b, Miklós Zoltán Ráczc, Cyrus Rashtchiand e
- aDepartment of Mathematics, University of Washington
- bUniversity of Washington
- cPrinceton University
- dDepartment of Computer Science & Engineering, University of California, San Diego
- eUniversity of California—San Diego
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
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.
TL;DRFor many classes of trees, including complete trees and spiders, this work provides algorithms that reconstruct the labels using only a polynomial number of traces, a stark contrast to known results on string trace reconstruction, which require exponentially many traces. (Semantic Scholar)