BARC talk by Chris Schwiegelshohn
Tuesday, 11 June, Chris Schwiegelshohn, assistant professor at DIAG Faculty of Sapienza University, will give a talk "Oblivious Dimension Reduction for k-Means"
Title:
Oblivious Dimension Reduction for k-Means
Abstract:
We show that for n points in d-dimensional Euclidean space, a data oblivious random projection of the columns onto m in O( log k+log log n eps^-6 log 1/eps) dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1±eps) factor. The previous-best upper bounds on m are O(log n eps^-2 ) given by a direct application of the Johnson-Lindenstrauss Lemma, and O( k ε^-2 ) given by [Cohen et al.-STOC’15].
BIO
Chris Schwiegelshohn is assistant professor at the DIAG faculty of Sapienza University. He completed his PhD in 2017 under the supervision of Christian Sohler at TU Dortmund and have been living in Italy since. He works mostly on algorithm design, with a focus on learning, streaming, and online algorithms.