  In this paper we give a first set of communication lower bounds for
distributed clustering problems, in particular, for k-center, k-median and
k-means. When the input is distributed across a large number of machines and
the number of clusters k is small, our lower bounds match the current best
upper bounds up to a logarithmic factor. We have designed a new composition
framework in our proofs for multiparty number-in-hand communication complexity
which may be of independent interest.
