Sanjeev Khanna is a Henry Salvatori Professor of Computer and Information Science at University of Pennsylvania. He received a Ph.D. in Computer Science from Stanford University in 1996. His doctoral work at Stanford received the 1996 Arthur Samuel prize for the best PhD dissertation in Computer Science.

Sanjeev’s primary research interests are in approximation algorithms and hardness of approximation, combinatorial optimization, and sublinear algorithms. He is an ACM Fellow, a Guggenheim Fellow, and a Sloan Fellow. Sanjeev is a recipient of best paper awards at SODA, SPAA, WINE, and ISTCS conferences as well as a test of time award at the ICDT conference. He is also a recipient of the S. Reid Warren, Jr. and Lindback awards for distinguished teaching at the University of Pennsylvania.

AG 1   Info

AG Audience

English

60 Minutes

Saarbrücken

Hierarchical clustering is a popular technique for organizing data as a rooted tree structure that simultaneously clusters data at multiple levels of granularity. A well-studied recent objective function views the input as a weighted graph with edges indicating similarity between the data points, and focuses on finding a tree that minimizes the cost of hierarchical partitioning. The resulting optimization problem is NP-hard, and previous algorithms for approximating this objective require at least linear time/space. In this talk, we will consider algorithms for hierarchical clustering that use sublinear resources (space, time, and communication).

Specifically, we will present sublinear algorithms for hierarchical clustering in the streaming model (space), in the query model (time), and in the MPC model (communication). At the core of our algorithmic results is a connection between hierarchical clustering and a suitably relaxed notion of cut sparsifiers of graphs that lends itself to efficient sublinear algorithms. We complement our algorithmic results by establishing nearly matching lower bounds that rule out algorithms with better performance guarantees in each of these models.

This is joint work with Arpit Agarwal, Huan Li, and Prathamesh Patil.

Roohani Sharma

+49 681 9325 1116

Zoom

988 5655 4581

passcode not visible

logged in users only

If you wish to attend the talk but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.