Event News

Talk on "From Hierarchical Clustering to Phylogenetic CSPs" by Vaggos Chatziafratis (UC Santa Cruz)

We are pleased to inform you about the upcoming seminar by Vaggos Chatziafratis (UC Santa Cruz) titled:"From Hierarchical Clustering to Phylogenetic CSPs" Everyone interested is cordially invited to attend!


From Hierarchical Clustering to Phylogenetic CSPs


Hierarchical Clustering (HC) is a widely studied problem in unsupervised learning and exploratory data analysis, usually tackled by simple agglomerative procedures like average-linkage, single-linkage or complete-linkage. Applications of HC include reasoning about text documents, understanding the Evolution of species and the Tree of life, decomposing social networks like Facebook, or even organizing large data centers efficiently. Surprisingly, despite the plethora of heuristics for tackling the problem, until recently there was no optimization objective associated with it; this is in stark contrast with flat clustering objectives like k-means, k-median and k-center. In this talk, we will give an overview of the optimization objectives for Hierarchical Clustering, we will discuss connections to Phylogenetic and Triplet Reconstruction methods, we will see some simple algorithms to find approximate solutions, and finally we will discuss some recent hardness of approximation results and new connections to the notion of approximation resistance of CSPs. Most of the talk on approximation algorithms is based on works jointly with Moses Charikar and Rad Niazadeh, and most of the talk on Phylogenetic CSPs hardness is joint with Konstantin Makarychev.

Speaker Bio:

Vaggos Chatziafratis is an Assistant Professor of Computer Science & Engineering at the University of California in Santa Cruz, where he is part of the Theoretical Computer Science group. His research lies at the intersection of approximation algorithms and machine learning, focusing on the design and analysis of approximation algorithms and hardness for clustering problems and on understanding neural networks through the lens of dynamical systems. Vaggos completed his MS and PhD at Stanford University in the Computer Science Department, where he was advised by Tim Roughgarden and Moses Charikar. Before Stanford, he finished with a Diploma from the ECE department of the National Technical University of Athens.
Before joining UC Santa Cruz, he did a postdoc at Google Research in New York hosted by Vahab Mirrokni and Mohammad Mahdian, working on hierarchical clustering with the graph mining team. He also did a postdoc at Northwestern working with Konstantin Makarychev, Aravindan Vijayaraghavan and Samir Khuller. Vaggos is the recipient of a FODSI postdoc fellowship at MIT (under Piotr Indyk) and Northeastern. His research at UCSC has been supported by a Hellman Fellowship.


13:30 - 14:30 / Monday , May . 20th, 2024


NII 1810




If you would like to join, please contact by email.
Email :yyoshida[at]nii.ac.jp