Tree trace reconstruction using subtraces

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 used combinatorial methods to show that $\exp (\mathcal{O}(k{\log }_{k}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.

13 pages, 2 figures