Abstract

The two most popular objectivesoptimized 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 thegoal is to classify the input point-set into k clusters such that the k-means(resp. k-median) objective is minimized. The best-known inapproximabilityfactor 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 ofapproximating these problems in various L_p-metrics.

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

Time

6月4日（星期二）14:00-15:00

Speaker

Karthik C. S. is a Ph.D. student of Prof. IritDinur at the Weizmann Institute of Science and is expected to graduate in June2019. He has obtained a masters degree in theoretical computer science fromEcole Normale Superieure, Lyon, in July 2014.

His research interests areprimarily in and around complexity theory with a focus on Hardness ofApproximation and Hardness Amplification in Fine-Grained and Fixed-ParameterComplexity, PCPs, Communication Complexity, and computational aspects of FixedPoint Theorems. He is also a comedic improviser. 

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号