[Talks@IDSIA] Chris Schwiegelshohn: On the Local Structure of Stable Clustering Instances

Title: On the Local Structure of Stable Clustering Instances Abstract: As an optimization problem, clustering exhibits a striking phenomenon: It is generally regarded as easy in practice, while theory classifies it among the computationally intractable problems. To address this dichotomy, research has identified a number of conditions a data set must satisfy for a clustering to be (1) easily computable and (2) meaningful. In this talk we show that all previously proposed notions of struturedness of a data set are fundamentally local properties, i.e. the global optimum is in well defined sense close to a local optimum. As a corollary, this implies that the Local Search heuristic has strong performance guarantees for both the tasks of recovering the underlying optimal clustering and obtaining a clustering of small cost. Bio: Chris Schwiegelshohn is currently a post-doc in Sapienza, University of Rome. He did his Phd in Dortmund with a thesis on "Algorithms for Large-Scale Graph and Clustering Problems". Chris' research interests include streaming and approximation algorithms as well as machine learning. Date: 8th of February 2018, 12:00-13:00 Location: Manno, Galleria 1, 2nd floor, room G1-204 Registration: Pizza and drinks will be offered at the end of the talk. If you plan to attend, please register in a timely fashion at the following link so that we will have no shortage of food: https://doodle.com/poll/sp294b469e9x44bf <https://doodle.com/poll/sp294b469e9x44bf>