Reconstructing trees from traces

Sami Davies, Miklós Z. Rácz, Cyrus Rashtchian

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)2772-2810
Number of pages39
JournalAnnals of Applied Probability
Issue number6
StatePublished - Dec 2021

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


  • Deletion channel
  • Littlewood polynomials
  • Trace reconstruction
  • Tree trace reconstruction


Dive into the research topics of 'Reconstructing trees from traces'. Together they form a unique fingerprint.

Cite this