Tree trace reconstruction using subtraces

Tatiana Brailovskaya, Miklós Z. Rácz

Research output: Contribution to journalArticlepeer-review

Abstract

Tree trace reconstruction aims to learn the binary node labels of a tree, given independent samples of the tree passed through an appropriately defined deletion channel. In recent work, Davies, Rácz, and Rashtchian [10] used combinatorial methods to show that exp (O(k logk n)) samples suffice to reconstruct a complete k-ary tree with n nodes with high probability. We provide an alternative proof of this result, which allows us to generalize it to a broader class of tree topologies and deletion models. In our proofs we introduce the notion of a subtrace, which enables us to connect with and generalize recent mean-based complex analytic algorithms for string trace reconstruction.

Original languageEnglish (US)
Pages (from-to)629-641
Number of pages13
JournalJournal of Applied Probability
Volume60
Issue number2
DOIs
StatePublished - 2023

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • General Mathematics
  • Statistics, Probability and Uncertainty

Keywords

  • Trace reconstruction
  • statistical error correction
  • tree graphs

Fingerprint

Dive into the research topics of 'Tree trace reconstruction using subtraces'. Together they form a unique fingerprint.

Cite this