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"

Oblivious Dimension Reduction for k-Means

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].

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.

Read more