Karthik C. S.

According to our database, Karthik C. S. authored at least 47 papers between 2011 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Deterministic Replacement Path Covering.

Karthik C. S., Merav Parter

ACM Trans. Algorithms, October, 2024

Fairness of linear regression in decision making.

Vincent Cohen-Addad, Surya Teja Gavva, Karthik C. S., Claire Mathieu, Namrata

Int. J. Data Sci. Anal., September, 2024

Clustering categorical data: Soft rounding <i>k</i>-modes.

Surya Teja Gavva, Karthik C. S., Sharath Punna

Inf. Comput., January, 2024

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.

Karthik C. S., Pasin Manurangsi

Electron. Colloquium Comput. Complex., 2024

Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality.

Karthik C. S., Saladi Rahul

CoRR, 2024

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof.

Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

On Approximability of Steiner Tree in <i>ℓ_p</i>-metrics.

Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP.

Karthik C. S., Euiwoong Lee, Pasin Manurangsi

Proceedings of the 19th International Symposium on Parameterized and Exact Computation, 2024

Explicit Good Codes Approaching Distance 1 in Ulam Metric.

Elazar Goldenberg, Mursalin Habib, Karthik C. S.

Proceedings of the IEEE International Symposium on Information Theory, 2024

On Connections Between k-Coloring and Euclidean k-Means.

Enver Aman, Karthik C. S., Sharath Punna

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291).

Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, Meirav Zehavi, Martin G. Herold

Dagstuhl Reports, 2023

Inapproximability of Maximum Diameter Clustering for Few Clusters.

Henry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov

CoRR, 2023

On Steiner Trees of the Regular Simplex.

Henry L. Fleischmann, Guillermo A. Gamboa Q., Karthik C. S., Josef Matejka, Jakub Petr

CoRR, 2023

On Approximability of Steiner Tree in 𝓁_p-metrics.

Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.

CoRR, 2023

Impossibility of Depth Reduction in Explainable Clustering.

Chengyuan Deng, Surya Teja Gavva, Karthik C. S., Parth Patel, Adarsh Srinivasan

CoRR, 2023

Can You Solve Closest String Faster Than Exhaustive Search?

Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

On Complexity of 1-Center in Various Metrics.

Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin

Proceedings of the Approximation, 2023

2022

Clustering Categorical Data: Soft Rounding k-modes.

Surya Teja Gavva, Karthik C. S., Sharath Punna

CoRR, 2022

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓ_p-metrics.

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Obtaining Approximately Optimal and Diverse Solutions via Dispersion.

Jie Gao, Mayank Goswami, Karthik C. S., Meng-Tsung Tsai, Shih-Yu Tsai, Hao-Tsung Yang

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

Almost Polynomial Factor Inapproximability for Parameterized k-Clique.

Karthik C. S., Subhash Khot

Proceedings of the 37th Computational Complexity Conference, 2022

2021

On Communication Complexity of Fixed Point Computation.

Anat Ganor, Karthik C. S., Dömötör Pálvölgyi

ACM Trans. Economics and Comput., 2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics.

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

Electron. Colloquium Comput. Complex., 2021

Applications of Random Algebraic Constructions to Hardness of Approximation.

Boris Bukh, Karthik C. S., Bhargav Narayanan

Electron. Colloquium Comput. Complex., 2021

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

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

CoRR, 2021

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

Karthik C. S., Inbal Livni Navon

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

On Approximability of Clustering Problems Without Candidate Centers.

Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Toward a General Direct Product Testing Theorem.

Elazar Goldenberg, Karthik C. S.

ACM Trans. Comput. Theory, 2020

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms.

Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi

Algorithms, 2020

On Efficient Low Distortion Ultrametric Embedding.

Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde

Proceedings of the 37th International Conference on Machine Learning, 2020

2019

On the Complexity of Closest Pair via Polar-Pair of Point-Sets.

Roee David, Karthik C. S., Bundit Laekhanukit

SIAM J. Discret. Math., 2019

Hardness Amplification of Optimization Problems.

Elazar Goldenberg, Karthik C. S.

Electron. Colloquium Comput. Complex., 2019

Parameterized Intractability of Even Set and Shortest Vector Problem.

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

Electron. Colloquium Comput. Complex., 2019

Inapproximability of Clustering in Lp Metrics.

Vincent Cohen-Addad, Karthik C. S.

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

An Efficient Representation for Filtrations of Simplicial Complexes.

Jean-Daniel Boissonnat, Karthik C. S.

ACM Trans. Algorithms, 2018

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

Karthik C. S., Pasin Manurangsi

Electron. Colloquium Comput. Complex., 2018

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

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

Electron. Colloquium Comput. Complex., 2018

Towards a General Direct Product Testing Theorem.

Elazar Goldenberg, Karthik C. S.

Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

Communication Complexity of Correlated Equilibrium with Small Support.

Anat Ganor, Karthik C. S.

Proceedings of the Approximation, 2018

2017

Did the train reach its destination: The complexity of finding a witness.

Karthik C. S.

Inf. Process. Lett., 2017

On the Parameterized Complexity of Approximating Dominating Set.

Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

Electron. Colloquium Comput. Complex., 2017

Communication Complexity of Correlated Equilibrium in Two-Player Games.

Anat Ganor, Karthik C. S.

Electron. Colloquium Comput. Complex., 2017

Building Efficient and Compact Data Structures for Simplicial Complexes.

Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas

Algorithmica, 2017

Ham Sandwich is Equivalent to Borsuk-Ulam.

Karthik C. S., Arpan Saha

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

The Curse of Medium Dimension for Geometric Problems in Almost Every Norm.

Roee David, Karthik C. S., Bundit Laekhanukit

CoRR, 2016

On the Sensitivity Conjecture for Disjunctive Normal Forms.

Karthik C. S., Sébastien Tavenas

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

2011

A Few Equivalences of Wall-Sun-Sun Prime Conjecture

Arpan Saha, Karthik C. S.

CoRR, 2011