Karthik C. S. | DeepAI

AI Chat

Featured Co-authors

Pasin Manurangsi
58 publications
Jie Gao
54 publications
Édouard Bonnet
45 publications
Vincent Cohen-Addad
45 publications
Dániel Marx
44 publications
Merav Parter
36 publications
Euiwoong Lee
30 publications
Arnab Bhattacharyya
28 publications
Amir Abboud
27 publications
Mayank Goswami
20 publications
Saeed Seddighin
19 publications

∙ 06/03/2023

On Approximability of Steiner Tree in ℓ_p-metrics

In the Continuous Steiner Tree problem (CST), we are given as input a se...

0 Henry Fleischmann, et al. ∙

∙ 05/26/2023

Can You Solve Closest String Faster than Exhaustive Search?

We study the fundamental problem of finding the best string to represent...

0 Amir Abboud, et al. ∙

∙ 05/04/2023

Impossibility of Depth Reduction in Explainable Clustering

Over the last few years Explainable Clustering has gathered a lot of att...

0 Chengyuan Deng, et al. ∙

∙ 10/18/2022

Clustering Categorical Data: Soft Rounding k-modes

Over the last three decades, researchers have intensively explored vario...

0 Surya Teja Gavva, et al. ∙

∙ 02/21/2022

Obtaining Approximately Optimal and Diverse Solutions via Dispersion

There has been a long-standing interest in computing diverse solutions t...

0 Jie Gao, et al. ∙

∙ 12/07/2021

Almost Polynomial Factor Inapproximability for Parameterized k-Clique

The k-Clique problem is a canonical hard problem in parameterized comple...

0 Karthik C. S., et al. ∙

∙ 12/06/2021

On Complexity of 1-Center in Various Metrics

We consider the classic 1-center problem: Given a set P of n points in a...

0 Amir Abboud, et al. ∙

∙ 11/21/2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics

K-median and k-means are the two most popular objectives for clustering ...

0 Vincent Cohen-Addad, et al. ∙

∙ 11/10/2021

Applications of Random Algebraic Constructions to Hardness of Approximation

In this paper, we show how one may (efficiently) construct two types of ...

0 Boris Bukh, et al. ∙

∙ 09/30/2020

On Approximability of Clustering Problems Without Candidate Centers

The k-means objective is arguably the most widely-used cost function for...

0 Vincent Cohen-Addad, et al. ∙

∙ 09/06/2020

On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes

In the (k,h)-SetCover problem, we are given a collection 𝒮 of sets over ...

0 Karthik C. S., et al. ∙

∙ 08/15/2020

On Efficient Low Distortion Ultrametric Embedding

A classic problem in unsupervised learning and data analysis is to find ...

0 Vincent Cohen-Addad, et al. ∙

∙ 08/12/2020

Deterministic Replacement Path Covering

In this article, we provide a unified and simplified approach to derando...

0 Karthik C. S., et al. ∙

∙ 06/08/2020

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

Parameterization and approximation are two popular ways of coping with N...

0 Andreas Emil Feldmann, et al. ∙

∙ 09/24/2019

On Communication Complexity of Fixed Point Computation

Brouwer's fixed point theorem states that any continuous function from a...

0 Anat Ganor, et al. ∙

∙ 09/04/2019

Parameterized Intractability of Even Set and Shortest Vector Problem

The k-Even Set problem is a parameterized variant of the Minimum Distanc...

0 Arnab Bhattacharyya, et al. ∙

∙ 08/27/2019

Hardness Amplification of Optimization Problems

In this paper, we prove a general hardness amplification scheme for opti...

0 Elazar Goldenberg, et al. ∙

∙ 01/18/2019

Towards a General Direct Product Testing Theorem

The Direct Product encoding of a string a∈{0,1}^n on an underlying domai...

0 Elazar Goldenberg, et al. ∙

∙ 12/03/2018

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

Given a set of n points in R^d, the (monochromatic) Closest Pair proble...

0 Karthik C. S., et al. ∙

∙ 03/26/2018

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

The k-Even Set problem is a parameterized variant of the Minimum Distanc...

0 Arnab Bhattacharyya, et al. ∙

∙ 11/29/2017

On the Parameterized Complexity of Approximating Dominating Set

We study the parameterized complexity of approximating the k-Dominating ...

0 Karthik C. S., et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world