Clustering is one of the basic tasks one has to deal with in almost any large-scale analysis of data. In view of the great importance of this problem and it ubiquity, it should not be surprising that much experience with it has been acquired, and many ingenious techniques have been invented to deal with it. Still the theoretical foundations in this area are unsatisfactory. In this talk I will describe several possible lines along which such a theory may presumably be developed. I will specifically concentrate on several ideas that have emerged from the study of finite metric spaces, and on the notion of stable instances of hard computational problems. (The latter subject is from joint work with Yonatan Bilu).
Copyright. All Rights Reserved.