Approximation Barriers for Big Data Problems

Karthik C. S. (Department of Computer Science, Rutgers University)

Speaker	Karthik C. S. (Department of Computer Science, Rutgers University)
When	Aug 25, 2025 from 02:00 PM to 03:00 PM
Where	LH-111, First Floor
Add event to calendar	vCal iCal

SEMINAR TALK

Title: Approximation Barriers for Big Data Problems

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 for 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 has shown 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 has advanced the understanding of the ultimate limits of approximation of these problems by proving strong inapproximability results.