Reconstructing trees from traces

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

Research output: Contribution to journalArticlepeer-review

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

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

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

Fingerprint

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

Cite this