CAREER: Towards Optimal Approximabilities for Clustering

Clustering is the task of grouping given objects so that similar objects are in the same cluster and different objects are in different clusters. It is one of the most basic tasks in unsupervised machine learning, and clustering algorithms are run numerous times each day across every field dealing with data. This research aims to develop efficient clustering algorithms with improved performance guarantees and study the limitations of efficient algorithms. These goals will be achieved by creating algorithmic techniques that advance the state-of-the-art and building new connections between various fields of computer science and mathematics, including optimization, complexity theory, geometry, combinatorics, and analysis. The outcome of this project will be integrated into various courses in data science and approximation algorithms at both undergraduate and graduate levels. The education plan also includes training graduate students and increasing the participation of undergraduate students in theoretical computer science. The project is centered around two main directions, one for algorithms and one for hardness. The first algorithmic direction is to revisit the study of local search, a discrete analog of gradient descent. While the standard local search has been well studied, new types of local search algorithms incorporating convex optimization methods or Euclidean geometry were recently proposed. Understanding the power of these local search algorithms seems to require a new global analysis. Secondly, the investigator will study a recently introduced complexity hypothesis called the Johnson Coverage Hypothesis which, if true, will result in significantly better hardness results for clustering in Euclidean spaces. It already reveals exciting connections to other areas of mathematics and theoretical computer science that are worth further investigation. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.