BARC talk by Evangelos Pipis

Monday, 14 July 2025, Evangelos Pipis, master's student at the National Technical University of Athens, Greece, will give a talk on "Fitting Tree Metrics and Ultrametrics in Data Streams".

Abstract:
Fitting distances to tree metrics and ultrametrics (i.e., trees in which all leaves are equidistant from the root) are two widely used methods in hierarchical clustering. Given a positive distance function D on a set of elements, the goal is to find a tree or an ultrametric T containing all these elements such that the difference between the distances in T and those specified by D is minimized. It is thus natural to ask: can these problems be solved efficiently in the semi-streaming model? In this talk, we address this question for the first time and propose key techniques that may lead to further progress in large-scale settings.

Our contributions span various distance norms. First, we present a single-pass, linear-space, combinatorial algorithm that achieves a constant-factor approximation for the L0-fitting ultrametrics, and we prove that no exact algorithm exists even with exponential time. We further show that this algorithm yields an approximation for L1-fitting ultrametrics that nearly matches the best-known combinatorial result. We also study Linf-fitting ultrametrics, for which we provide a complete characterization. Finally, we extend all these results to tree metrics using only one additional pass, without asymptotically increasing the approximation factors.

This is joint work with Amir Carmel, Debarati Das (BARC alumni), and Evangelos Kipouridis (BARC alumni).

Bio:
Evangelos is currently a master’s student at the National Technical University of Athens, Greece. His main interests lie in theoretical computer science, with a focus on approximation and sublinear algorithms, as well as causal inference.

Host:
Mikkel Thorup