Vincent Cohen-Addad: Sublinear time algorithms for Euclidean clustering coresets and correlation clustering

For over 20 years, extracting information from massive data has been a major challenge in various fields. How fast can we obtain meaningful information from large datasets? In this talk we will survey recent results on two classic problems:

– Computing the mean of a set of points in R^d, for possibly large d.

– Computing a clustering of a dataset given pairwise similarities between the data elements.

We will see how this can be done in sublinear time without sacrificing much on the quality of the solution.

The work is based on the following works:

– Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn: NeurIPS 2021:

-Correlation Clustering in Constant Many Parallel Rounds. Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski: ICML 2021