Seminar Details

Given a rooted tree on n leaves, we define the natural “split-away” property for a triplet of leaves (u,v,w): w splits away from (u,v) if the lowest common ancestor (LCA) of {u,v,w} is closer to the root than LCA(u,v). While a unique tree can be reconstructed from the correct split-away information for all triplets, a critical question is what if the answers to some triplets are wrong. The question is motivated by the recent line of learning-augmented algorithms, where the split-away information can be computed by a machine learning-based oracle with possible errors. We introduce algorithms that construct partial trees—a data structure that follows the optimal tree’s structure until the leaf subsets are sufficiently small. We show that partial tree construction is possible with noisy triplet split-away queries. Applying our approach, we obtain improved algorithms for hierarchical clustering (HC), including an O(1)-approximation algorithm for Dasgupta’s HC objective in polynomial time and a (1-o(1))-approximation algorithm in O(n polylog{n}) time. Both results are known to be impossible under plausible hardness assumptions without the noisy triplet oracle. Furthermore, we demonstrate the broad applicability of our approach by obtaining improved results for related problems in computational biology.