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.
Original language | English (US) |
---|---|
Pages (from-to) | 2772-2810 |
Number of pages | 39 |
Journal | Annals of Applied Probability |
Volume | 31 |
Issue number | 6 |
DOIs | |
State | Published - Dec 2021 |
All Science Journal Classification (ASJC) codes
- Statistics and Probability
- Statistics, Probability and Uncertainty
Keywords
- Deletion channel
- Littlewood polynomials
- Trace reconstruction
- Tree trace reconstruction