You are here

Reconstructing trees from traces 

Samantha Davies, University of Washington
Thursday, May 2, 2019 - 11:00am to 12:00pm
PDL C-401

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. In this talk, I will define the problem and models, state our main results, and outline our techniques. 

Joint work with Cyrus Rashtchian and Miklos Z. Racz.
Event Type: 
Event Subcalendar: