Karthik C. S.
Karthik C. S.
Verified email at - Homepage
Cited by
Cited by
On the parameterized complexity of approximating dominating set
Karthik C. S., B Laekhanukit, P Manurangsi
Journal of the ACM, 2019
A survey on approximation in parameterized complexity: Hardness and algorithms
AE Feldmann, Karthik C. S., E Lee, P Manurangsi
Algorithms 13 (6), 146, 2020
Inapproximability of clustering in lp metrics
V Cohen-Addad, Karthik C. S.
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS …, 2019
On closest pair in euclidean metric: Monochromatic is as hard as bichromatic
Karthik C. S., P Manurangsi
Combinatorica 40 (4), 539-573, 2020
Building efficient and compact data structures for simplicial complexes
JD Boissonnat, Karthik C. S., S Tavenas
Algorithmica 79 (2), 530-567, 2017
On approximability of clustering problems without candidate centers
V Cohen-Addad, CS Karthik, E Lee
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021
Parameterized intractability of even set and shortest vector problem from gap-eth
A Bhattacharyya, S Ghoshal, K C. S., P Manurangsi
arXiv preprint arXiv:1803.09717, 2018
Parameterized Intractability of Even Set and Shortest<? brk?> Vector Problem
A Bhattacharyya, É Bonnet, L Egri, S Ghoshal, Karthik C. S., B Lin, ...
Journal of the ACM (JACM) 68 (3), 1-40, 2021
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in p-metrics
V Cohen-Addad, E Lee
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2022
On the complexity of closest pair via polar-pair of point-sets
R David, B Laekhanukit
SIAM Journal on Discrete Mathematics 33 (1), 509-527, 2019
An efficient representation for filtrations of simplicial complexes
JD Boissonnat, K CS
ACM Transactions on Algorithms (TALG) 14 (4), 1-21, 2018
Did the train reach its destination: The complexity of finding a witness
CS Karthik
Information processing letters 121, 17-21, 2017
Communication complexity of correlated equilibrium in two-player games
A Ganor
arXiv preprint arXiv:1704.01104, 2017
Deterministic replacement path covering
CS Karthik, M Parter
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021
Almost polynomial factor inapproximability for parameterized k-clique
CS Karthik, S Khot
37th Computational Complexity Conference (CCC 2022), 2022
On the sensitivity conjecture for disjunctive normal forms
S Tavenas
arXiv preprint arXiv:1607.05189, 2016
On communication complexity of fixed point computation
A Ganor, K C. S., D Pálvölgyi
ACM transactions on economics and computation 9 (4), 1-27, 2021
On hardness of approximation of parameterized set cover and label cover: Threshold graphs from error correcting codes
CS Karthik, LN Inbal
Symposium on Simplicity in Algorithms (SOSA), 210-223, 2021
On efficient low distortion ultrametric embedding
V Cohen-Addad, CS Karthik, G Lagarde
International Conference on Machine Learning, 2078-2088, 2020
Hardness amplification of optimization problems
E Goldenberg
arXiv preprint arXiv:1908.10248, 2019
The system can't perform the operation now. Try again later.
Articles 1–20