Seminars

View all Seminars  |  Download ICal for this event

Approximation Barriers for Big Data Problems

Series: Department Seminar

Speaker: Prof. Karthik C. S., Rutgers University, USA

Date/Time: Aug 21 10:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
Many of today\'s significant challenges, from organizing massive datasets to identifying similar points in large datasets or calculating the similarity between DNA sequences, rely on solving fundamental computational problems. As datasets grow in size, a common strategy is to relax the requirement for an exact solution and instead use an approximation algorithm to gain a significant speedup. My research addresses this from a theoretical standpoint. By studying the hardness of approximation, my work helps establish the fundamental limits of this speed??accuracy trade-off, clarifying for key problems when we cannot significantly improve upon the performance of known algorithms, even when allowing approximate solutions.

In this talk, I will present my contributions to this area through two key research programs.

First, I will address problems traditionally considered solvable in polynomial time, such as computing the closest pair of points in large-scale data or finding a set cover of fixed size, a task that routinely arises in computational proteomics and peptide identification. My work in fine-grained and fixed-parameter complexity shows that, for some of these core problems, no approximation algorithm can offer a significant asymptotic speedup over exact methods.

Second, I will turn to NP-hard geometric optimization problems such as clustering and Steiner tree, which are central to machine learning, logistics, and network design. For these problems, approximation algorithms are unavoidable. My work advances the understanding of the ultimate limits of approximation of these problems by proving strong inapproximability results.

Speaker Bio:
Karthik C. S. is an Assistant Professor in the Department of Computer Science at Rutgers University supported by an NSF CAREER Award, a Simons Foundation Junior Faculty Fellowship, and another grant from the National Science Foundation. He received his Ph.D. in 2019 from Weizmann Institute of Science advised by Irit Dinur, and his M.S. in 2014 from École Normale Supérieure de Lyon. He has held postdoctoral appointments at Tel Aviv University (hosted by Amir Shpilka) and New York University (hosted by Subhash Khot). He is broadly interested in complexity theory and discrete geometry, with an emphasis on hardness of approximation, fine-grained complexity, and parameterized complexity.

Host Faculty: R Govindarajan