Publications [#379106] of Tatiana I Brailovskaya

Papers Published

1. Brailovskaya, T; Rácz, MZ, Tree trace reconstruction using subtraces, Journal of Applied Probability, vol. 60 no. 2 (January, 2023), pp. 629-641 [doi]
   (last updated on 2024/11/20)

   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.