27 citations · 41 across the 8 of their papers we have counts for
13 papers
A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering
Karthik C. S., Euiwoong Lee, Yuval Rabani +2
Metric -minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achie…
Accelerating Scientific Research with Gemini: Case Studies and Common Techniques
David P. Woodruff, Vincent Cohen-Addad, Lalit Jain +33
Recent advances in large language models (LLMs) have opened new avenues for accelerating scientific research. While models are increasingly capable of assisting with routine tasks,…
On Approximability of Min-Sum Clustering
Karthik C. S., Euiwoong Lee, Yuval Rabani +2
The min-sum -clustering problem is to partition an input set into clusters to minimize . Although $\ell_2^2…
On connections between k-coloring and Euclidean k-means
Enver Aman, Karthik C. S., Sharath Punna
In the Euclidean -means problems we are given as input a set of points in and the goal is to find a set of points , so as to mini…
On Steiner Trees of the Regular Simplex
Henry Fleischmann, Guillermo A. Gamboa Q., Karthik C. S. +2
In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the -metric space and the goal is to find the minimum-cost tree connectin…
Inapproximability of Maximum Diameter Clustering for Few Clusters
Henry Fleischmann, Kyrylo Karlov, Karthik C. S. +2
In the Max-k-diameter problem, we are given a set of points in a metric space, and the goal is to partition the input points into k parts such that the maximum pairwise distance be…
On Approximability of Steiner Tree in -metrics
Henry Fleischmann, Surya Teja Gavva, Karthik C. S
In the Continuous Steiner Tree problem (CST), we are given as input a set of points (called terminals) in a metric space and ask for the minimum-cost tree connecting them. Addition…
Impossibility of Depth Reduction in Explainable Clustering
Chengyuan Deng, Surya Teja Gavva, Karthik C. S. +2
Over the last few years Explainable Clustering has gathered a lot of attention. Dasgupta et al. [ICML'20] initiated the study of explainable -means and -median clustering pro…
Clustering Categorical Data: Soft Rounding k-modes
Surya Teja Gavva, Karthik C. S., Sharath Punna
Over the last three decades, researchers have intensively explored various clustering tools for categorical data analysis. Despite the proposal of various clustering algorithms, th…
Almost Polynomial Factor Inapproximability for Parameterized k-Clique
Karthik C. S., Subhash Khot
The k-Clique problem is a canonical hard problem in parameterized complexity. In this paper, we study the parameterized complexity of approximating the k-Clique problem where an in…
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
K-median and k-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, parti…
On Approximability of Clustering Problems Without Candidate Centers
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
The k-means objective is arguably the most widely-used cost function for modeling clustering tasks in a metric space. In practice and historically, k-means is thought of in a conti…
Building Efficient and Compact Data Structures for Simplicial Complexes
Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas
The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range…