We consider the following clustering with outliers problem: Given a set of points X−11n , such that there is some point z−11n for which at least of the points are -correlated with z, find z. We call such a point z a () -center of X.

In this work we give lower and upper bounds for the task of finding a () -center. Our main upper bound shows that for values of and that are larger than 1/polylog(n), there exists a polynomial time algorithm that finds a (−o(1)−o(1)) -center. Moreover, it outputs a list of centers explaining all of the clusters in the input. Our main lower bound shows that given a set for which there exists a () -center, it is hard to find even a (nc) -center for some constant c and =1poly(n)=1poly(n) .