The two most popular objectives optimized in clustering algorithms are k-means and k-median. The k-means (resp. k-median) problem in the L_p-metric is specified by n points as input and the goal is to classify the input point-set into k clusters such that the k-means (resp. k-median) objective is minimized. The best-known inapproximability factor in literature for these NP-hard problems in L_p-metrics were below 1.01. In this talk, we take a significant step to improve the hardness of approximating these problems in various L_p-metrics.

Our techniques are inspired by the tools and perspectives developed in fine-grained complexity in the last couple of years. In particular, there is an interesting interplay between geometric embeddings and communication protocols that will be emphasized and exploited in our proofs.