UCSB CS Theory Colloquium Series

Fall 2021

Friday, October 22, 2pm, Phelps 2510
                Speaker: Sanjoy Dasgupta (UC San Diego)
                Title: Some recent theoretical directions in clustering
Abstract:
I’ll talk about two recent lines of work on clustering that have seen quite a bit of algorithmic progress.

1. Cost functions for hierarchical clustering.

The development of algorithms for hierarchical clustering has traditionally been hindered by a lack of precise objective functions. I’ll talk about how this situation has recently been remedied. This will mostly be about the following paper as well as more recent progress by Charikar, Chatziafratis, Cohen-Addad, Mathieu, Moseley, and Wang.

A cost function for similarity-based hierarchical clustering. STOC 2016.

2. Explainable k-means clustering.

Common clustering algorithms return clusters that are arbitrary subsets of the data, or at best convex regions of space. What is the price of asking for simpler (and therefore more “explainable”) clusters, e.g. hyperrectangular and based on just a few features? This will mostly be about the following paper as well as more recent work by Laber, Makarychev, Mirrokni, Svensson, and others.

(With Cyrus Rashtchian, Michal Moshkovitz, and Nave Frost) Explainable k-means and k-medians clustering. ICML 2020.