Karthik C. S.

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 83

Top Topics

Error Correcting

Parameterized Complexity

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Karthik C. S., Pasin Manurangsi
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. Electron. Colloquium Comput. Complex. (2024)
Elazar Goldenberg, Mursalin Habib, Karthik C. S.
Explicit Good Codes Approaching Distance 1 in Ulam Metric. CoRR (2024)
Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. SOSA (2024)
Surya Teja Gavva, Karthik C. S., Sharath Punna
-modes. Inf. Comput. 296 (2024)
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP. CoRR (2024)
Enver Aman, Karthik C. S., Sharath Punna
On connections between k-coloring and Euclidean k-means. CoRR (2024)
Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.
-metrics. SODA (2024)
Karthik C. S., Saladi Rahul
Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality. CoRR (2024)
Vincent Cohen-Addad, Surya Teja Gavva, Karthik C. S., Claire Mathieu, Namrata
Fairness of linear regression in decision making. Int. J. Data Sci. Anal. 18 (3) (2024)
Chengyuan Deng, Surya Teja Gavva, Karthik C. S., Parth Patel, Adarsh Srinivasan
Impossibility of Depth Reduction in Explainable Clustering. CoRR (2023)
Henry Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov
Inapproximability of Maximum Diameter Clustering for Few Clusters. CoRR (2023)
Henry Fleischmann, Guillermo A. Gamboa Q., Karthik C. S., Josef Matejka, Jakub Petr
On Steiner Trees of the Regular Simplex. CoRR (2023)
Henry Fleischmann, Surya Teja Gavva, Karthik C. S.
-metrics. CoRR (2023)
Karthik C. S., Pasin Manurangsi
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. CoRR (2023)
Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, Meirav Zehavi, Martin Herold
Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291). Dagstuhl Reports 13 (7) (2023)
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
Can You Solve Closest String Faster Than Exhaustive Search? ESA (2023)
Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. CoRR (2023)
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
On Complexity of 1-Center in Various Metrics. APPROX/RANDOM (2023)
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
Can You Solve Closest String Faster than Exhaustive Search? CoRR (2023)
Jie Gao, Mayank Goswami, Karthik C. S., Meng-Tsung Tsai, Shih-Yu Tsai, Hao-Tsung Yang
Obtaining Approximately Optimal and Diverse Solutions via Dispersion. LATIN (2022)
Jie Gao, Mayank Goswami, Karthik C. S., Meng-Tsung Tsai, Shih-Yu Tsai, Hao-Tsung Yang
Obtaining Approximately Optimal and Diverse Solutions via Dispersion. CoRR (2022)
Surya Teja Gavva, Karthik C. S., Sharath Punna
Clustering Categorical Data: Soft Rounding k-modes. CoRR (2022)
Karthik C. S., Subhash Khot
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. CCC (2022)
Boris Bukh, Karthik C. S., Bhargav Narayanan
Applications of Random Algebraic Constructions to Hardness of Approximation. FOCS (2022)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
-metrics. SODA (2022)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. J. ACM 68 (3) (2021)
Boris Bukh, Karthik C. S., Bhargav Narayanan
Applications of Random Algebraic Constructions to Hardness of Approximation. FOCS (2021)
Anat Ganor, Karthik C. S., Dömötör Pálvölgyi
On Communication Complexity of Fixed Point Computation. ACM Trans. Economics and Comput. 9 (4) (2021)
Karthik C. S., Subhash Khot
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. CoRR (2021)
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
On Complexity of 1-Center in Various Metrics. CoRR (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics. CoRR (2021)
Karthik C. S., Merav Parter
Deterministic Replacement Path Covering. SODA (2021)
Boris Bukh, Karthik C. S., Bhargav Narayanan
Applications of Random Algebraic Constructions to Hardness of Approximation. Electron. Colloquium Comput. Complex. 28 (2021)
Karthik C. S., Inbal Livni Navon
On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes. SOSA (2021)
Boris Bukh, Karthik C. S., Bhargav Narayanan
Applications of Random Algebraic Constructions to Hardness of Approximation. CoRR (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
On Approximability of Clustering Problems Without Candidate Centers. SODA (2021)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics. Electron. Colloquium Comput. Complex. 28 (2021)
Karthik C. S., Inbal Livni Navon
On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes. CoRR (2020)
Karthik C. S., Pasin Manurangsi
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. Comb. 40 (4) (2020)
Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde
On Efficient Low Distortion Ultrametric Embedding. CoRR (2020)
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms 13 (6) (2020)
Elazar Goldenberg, Karthik C. S.
Toward a General Direct Product Testing Theorem. ACM Trans. Comput. Theory 12 (1) (2020)
Elazar Goldenberg, Karthik C. S.
Hardness Amplification of Optimization Problems. ITCS (2020)
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Electron. Colloquium Comput. Complex. 27 (2020)
Karthik C. S., Merav Parter
Deterministic Replacement Path Covering. CoRR (2020)
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
On Approximability of Clustering Problems Without Candidate Centers. CoRR (2020)
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. CoRR (2020)
Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde
On Efficient Low Distortion Ultrametric Embedding. ICML (2020)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. Electron. Colloquium Comput. Complex. 26 (2019)
Roee David, Karthik C. S., Bundit Laekhanukit
On the Complexity of Closest Pair via Polar-Pair of Point-Sets. SIAM J. Discret. Math. 33 (1) (2019)
Karthik C. S., Pasin Manurangsi
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. ITCS (2019)
Vincent Cohen-Addad, Karthik C. S.
Inapproximability of Clustering in Lp Metrics. FOCS (2019)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. CoRR (2019)
Elazar Goldenberg, Karthik C. S.
Hardness Amplification of Optimization Problems. Electron. Colloquium Comput. Complex. 26 (2019)
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
On the Parameterized Complexity of Approximating Dominating Set. J. ACM 66 (5) (2019)
Elazar Goldenberg, Karthik C. S.
Towards a General Direct Product Testing Theorem. CoRR (2019)
Anat Ganor, Karthik C. S., Dömötör Pálvölgyi
On Communication Complexity of Fixed Point Computation. CoRR (2019)
Elazar Goldenberg, Karthik C. S.
Hardness Amplification of Optimization Problems. CoRR (2019)
Roee David, Karthik C. S., Bundit Laekhanukit
On the Complexity of Closest Pair via Polar-Pair of Point-Sets. SoCG (2018)
Elazar Goldenberg, Karthik C. S.
Towards a General Direct Product Testing Theorem. FSTTCS (2018)
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
On the parameterized complexity of approximating dominating set. STOC (2018)
Anat Ganor, Karthik C. S.
Communication Complexity of Correlated Equilibrium with Small Support. APPROX-RANDOM (2018)
Jean-Daniel Boissonnat, Karthik C. S.
An Efficient Representation for Filtrations of Simplicial Complexes. ACM Trans. Algorithms 14 (4) (2018)
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. ICALP (2018)
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. CoRR (2018)
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. Electron. Colloquium Comput. Complex. 25 (2018)
Karthik C. S., Pasin Manurangsi
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. Electron. Colloquium Comput. Complex. 25 (2018)
Karthik C. S., Pasin Manurangsi
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. CoRR (2018)
Karthik C. S., Arpan Saha
Ham Sandwich is Equivalent to Borsuk-Ulam. SoCG (2017)
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
On the Parameterized Complexity of Approximating Dominating Set. Electron. Colloquium Comput. Complex. 24 (2017)
Karthik C. S.
Did the train reach its destination: The complexity of finding a witness. Inf. Process. Lett. 121 (2017)
Anat Ganor, Karthik C. S.
Communication Complexity of Correlated Equilibrium in Two-Player Games. CoRR (2017)
Jean-Daniel Boissonnat, Karthik C. S.
An Efficient Representation for Filtrations of Simplicial Complexes. SODA (2017)
Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas
Building Efficient and Compact Data Structures for Simplicial Complexes. Algorithmica 79 (2) (2017)
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
On the Parameterized Complexity of Approximating Dominating Set. CoRR (2017)
Anat Ganor, Karthik C. S.
Communication Complexity of Correlated Equilibrium in Two-Player Games. Electron. Colloquium Comput. Complex. 24 (2017)
Karthik C. S.
Did the Train Reach its Destination: The Complexity of Finding a Witness. CoRR (2016)
Karthik C. S., Sébastien Tavenas
On the Sensitivity Conjecture for Disjunctive Normal Forms. CoRR (2016)
Roee David, Karthik C. S., Bundit Laekhanukit
The Curse of Medium Dimension for Geometric Problems in Almost Every Norm. CoRR (2016)
Karthik C. S., Sébastien Tavenas
On the Sensitivity Conjecture for Disjunctive Normal Forms. FSTTCS (2016)
Jean-Daniel Boissonnat, Karthik C. S.
An Efficient Representation for Filtrations of Simplicial Complexes. CoRR (2016)
Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas
Building Efficient and Compact Data Structures for Simplicial Complexes. CoRR (2015)
Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas
Building Efficient and Compact Data Structures for Simplicial Complexes. SoCG (2015)
Arpan Saha, Karthik C. S.
A Few Equivalences of Wall-Sun-Sun Prime Conjecture CoRR (2011)