DoDaS & FAIR Guest: Chris Schwiegelshohn
Chris Schwiegelshohn is a joint guest of the FAIR research profile & DoDaS
Title: Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
Abstract: In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key role. For the classic k-median and k-means problems, there are no known deterministic dimensionality reduction procedure or coreset construction that avoid an exponential dependency on the input dimension d, the precision parameter ε or k. Furthermore, there is no coreset construction that succeeds with probability 1−1/n and whose size does not depend on the number of input points, n. This has led researchers in the area to ask what is the power of randomness for clustering sketches. Similarly, the best approximation ratio achievable deterministically without a complexity exponential in the dimension are Ω(1) for both k-median and k-means, even when allowing a complexity FPT in the number of clusters k. This stands in sharp contrast with the (1+ε)-approximation achievable in that case, when allowing randomization.
In this talk, we discuss deterministic sketch constructions for clustering, whose size bounds are close to the best-known randomized ones. We also show a deterministic algorithm for computing a (1+ε)-approximation to k-median and k-means in high dimensional Euclidean spaces in time 2^(k^2/ε^O(1)) poly(nd), close to the best randomized complexity. Furthermore, our new insights on sketches also yield a randomized coreset construction that uses uniform sampling, and improves over recent results by a factor k.
Short Bio: Chris is a home grown researcher, having completed his PhD under the supervision of Christian Sohler at TU Dortmund. Subsequently, he joined Sapienza, University of Rome, first as a Postdoc hosted by Stefano Leonardi and then as a faculty member. In 2020, he joined Aarhus University where he is now associate professor in the Algorithms, Data Structures and Foundations of Machine Learning group. Chris' research focusses on algorithm design in general, with an emphasis on sketching, streaming and learning algorithms, as well as approximation and online algorithms.