CS Events Monthly View

Faculty Candidate Talk

New Arenas in Hardness of Approximation


Download as iCal file

Tuesday, February 09, 2021, 10:30am


Speaker: Karthik Srikanta


Karthik is currently a Postdoctoral Fellow at the Courant Institute of Mathematical Sciences, New York University, hosted by Subhash Khot. He received his Ph.D. in 2019 from Weizmann Institute of Science where he was advised by Irit Dinur. Prior to that, he obtained his M.S. from Ecole Normale Superieure in Lyon. His main research interests are in the intersection of complexity theory and combinatorial geometry.

Location : Via Zoom Recording

Event Type: Faculty Candidate Talk

Abstract: In this talk, I will introduce the mathematically-rich area of hardness of approximation through the recent inapproximability results for selected geometric problems whose difficulty ranges from being in P (e.g., closest pair problem) to being NP-hard (e.g., k-means clustering problem). The closest pair problem is a fundamental problem in computational geometry where given a set of n points in high dimensions (say log n dimensions) as input, we are required to find the closest pair of points. This problem can be solved in a straightforward manner in roughly O(n^2) time (by computing all pairwise distances), but can it be solved faster, in say O(n^1.9) time? If not, is there at least a fast algorithm that finds a pair of points that are close to being the nearest? An important task in unsupervised learning is k-means clustering. In this problem, given a set of n points and an integer k, we are asked to find a partition of the point-set into k clusters that minimizes the k-means objective. This problem is NP-hard and thus believed to not admit any polynomial (in n) time algorithm. But is there an algorithm running in polynomial time that can find k clusters whose k-means objective is only a 2 factor away from an optimal clustering solution? In this talk, I will present the recent advances on the above long standing questions and also briefly sketch the landscape of the complexity of geometric problems and the important open questions that need to be addressed therein. I will also highlight the symbiosis in the ideas needed to answer the aforementioned questions on closest pair and clustering problems, which might seem a-priori very different.

Contact  Host: Dr. Aaron Bernstein

Please view the recording through the following link