Karthik C. S.

105 papers A* 17A 8B 3Journal 72Unranked 5
YearRankTypeTitle / Venue / Authors
2026 J jnl
Accelerating Scientific Research with Gemini: Case Studies and Common Techniques.
CoRR
David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, MohammadHossein Bateni, Simina Brânzei, Michael P. Brenner, Lin Chen, Ying Feng, Lance Fortnow, Gang Fu, Ziyi Guan, Zahra Hadizadeh, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Adel Javanmard, Karthik C. S., Ken-ichi Kawarabayashi, Ravi Kumar, Silvio Lattanzi, Euiwoong Lee, Yi Li, Ioannis Panageas, Dimitris Paparas, Benjamin Przybocki, Bernardo Subercaseaux, Ola Svensson, Shayan Taherijam, Xuan Wu, Eylon Yogev, Morteza Zadimoghaddam, Samson Zhou, Yossi Matias, James Manyika, Vahab Mirrokni
2026 J jnl
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces.
CoRR
Vincent Cohen-Addad, Karthik C. S., David Saulpic, Chris Schwiegelshohn
2026 J jnl
Fine-Grained Complexity of Continuous Euclidean k-Center.
CoRR
Lotte Blank, Karl Bringmann, Parinya Chalermsook, Karthik C. S., Benedikt Kolbe, Hung Le, Geert van Wordragen
2026 J jnl
Impossibility of depth reduction in explainable clustering.
Inf. Comput.
Chengyuan Deng, Surya Teja Gavva, Karthik C. S., Parth Patel, Adarsh Srinivasan
2026 J jnl
Near-Optimal Bounds for Parameterized Euclidean k-means.
CoRR
Vincent Cohen-Addad, Karthik C. S., David Saulpic, Chris Schwiegelshohn
2026 A conf
Range Longest Increasing Subsequence and Its Relatives.
ITCS
Karthik C. S., Saladi Rahul
2025 J jnl
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric.
CoRR
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., Michal Koucký
2025 J jnl
Explicit Good Codes Approaching Distance 1 in Ulam Metric.
IEEE Trans. Inf. Theory
Elazar Goldenberg, Mursalin Habib, Karthik C. S.
2025 A conf
Hardness of Median and Center in the Ulam Metric.
ESA
Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S.
2025 J jnl
Hardness of Median and Center in the Ulam Metric.
CoRR
Nick Fischer, Elazar Goldenberg, Mursalin Habib, Karthik C. S.
2025 A* conf
Inapproximability of Maximum Diameter Clustering for Few Clusters.
SODA
Henry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov
2025 A* conf
Maximum Span Hypothesis: A Potentially Weaker Assumption than Gap-ETH for Parameterized Complexity.
SODA
Karthik C. S., Subhash Khot
2025 A* conf
Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity.
STOC
Mitali Bafna, Karthik C. S., Dor Minzer
2025 J jnl
On Approximability of Steiner Tree in ℓ
TheoretiCS
Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.
2025 A* conf
On Approximability of ℓ₂² Min-Sum Clustering.
SoCG
Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou
2025 J jnl
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP.
Algorithmica
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2025 J jnl
On Steiner Trees of the regular simplex.
J. Comput. Geom.
Henry L. Fleischmann, Guillermo Gamboa Quintero, Karthik C. S., Josef Matejka, Jakub Petr
2024 J jnl
Clustering categorical data: Soft rounding
Inf. Comput.
Surya Teja Gavva, Karthik C. S., Sharath Punna
2024 — conf
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof.
SOSA
Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza
2024 J jnl
Deterministic Replacement Path Covering.
ACM Trans. Algorithms
Karthik C. S., Merav Parter
2024 B conf
Explicit Good Codes Approaching Distance 1 in Ulam Metric.
ISIT
Elazar Goldenberg, Mursalin Habib, Karthik C. S.
2024 J jnl
Explicit Good Codes Approaching Distance 1 in Ulam Metric.
CoRR
Elazar Goldenberg, Mursalin Habib, Karthik C. S.
2024 J jnl
Fairness of linear regression in decision making.
Int. J. Data Sci. Anal.
Vincent Cohen-Addad, Surya Teja Gavva, Karthik C. S., Claire Mathieu, Namrata
2024 A* conf
On Approximability of Steiner Tree in
SODA
Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.
2024 J jnl
On Approximability of ℓ
CoRR
Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou
2024 A conf
On Connections Between k-Coloring and Euclidean k-Means.
ESA
Enver Aman, Karthik C. S., Sharath Punna
2024 B conf
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP.
IPEC
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2024 J jnl
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP.
CoRR
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2024 J jnl
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.
Electron. Colloquium Comput. Complex.
Karthik C. S., Pasin Manurangsi
2024 J jnl
On connections between k-coloring and Euclidean k-means.
CoRR
Enver Aman, Karthik C. S., Sharath Punna
2024 J jnl
Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality.
CoRR
Karthik C. S., Saladi Rahul
2023 A conf
Can You Solve Closest String Faster Than Exhaustive Search?
ESA
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
2023 J jnl
Can You Solve Closest String Faster than Exhaustive Search?
CoRR
Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier
2023 J jnl
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof.
CoRR
Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza
2023 J jnl
Impossibility of Depth Reduction in Explainable Clustering.
CoRR
Chengyuan Deng, Surya Teja Gavva, Karthik C. S., Parth Patel, Adarsh Srinivasan
2023 J jnl
Inapproximability of Maximum Diameter Clustering for Few Clusters.
CoRR
Henry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov
2023 J jnl
On Approximability of Steiner Tree in 𝓁
CoRR
Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.
2023 A conf
On Complexity of 1-Center in Various Metrics.
APPROX/RANDOM
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
2023 J jnl
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.
CoRR
Karthik C. S., Pasin Manurangsi
2023 J jnl
On Steiner Trees of the Regular Simplex.
CoRR
Henry L. Fleischmann, Guillermo Gamboa Quintero, Karthik C. S., Josef Matejka, Jakub Petr
2023 J jnl
Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291).
Dagstuhl Reports
Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, Meirav Zehavi, Martin G. Herold
2022 A conf
Almost Polynomial Factor Inapproximability for Parameterized k-Clique.
CCC
Karthik C. S., Subhash Khot
2022 J jnl
Clustering Categorical Data: Soft Rounding k-modes.
CoRR
Surya Teja Gavva, Karthik C. S., Sharath Punna
2022 A* conf
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓ
SODA
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2022 B conf
Obtaining Approximately Optimal and Diverse Solutions via Dispersion.
LATIN
Jie Gao, Mayank Goswami, Karthik C. S., Meng-Tsung Tsai, Shih-Yu Tsai, Hao-Tsung Yang
2022 J jnl
Obtaining Approximately Optimal and Diverse Solutions via Dispersion.
CoRR
Jie Gao, Mayank Goswami, Karthik C. S., Meng-Tsung Tsai, Shih-Yu Tsai, Hao-Tsung Yang
2021 J jnl
Almost Polynomial Factor Inapproximability for Parameterized k-Clique.
CoRR
Karthik C. S., Subhash Khot
2021 A* conf
Applications of Random Algebraic Constructions to Hardness of Approximation.
FOCS
Boris Bukh, Karthik C. S., Bhargav Narayanan
2021 J jnl
Applications of Random Algebraic Constructions to Hardness of Approximation.
CoRR
Boris Bukh, Karthik C. S., Bhargav Narayanan
2021 J jnl
Applications of Random Algebraic Constructions to Hardness of Approximation.
Electron. Colloquium Comput. Complex.
Boris Bukh, Karthik C. S., Bhargav Narayanan
2021 A* conf
Deterministic Replacement Path Covering.
SODA
Karthik C. S., Merav Parter
2021 J jnl
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics.
Electron. Colloquium Comput. Complex.
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2021 J jnl
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics.
CoRR
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2021 A* conf
On Approximability of Clustering Problems Without Candidate Centers.
SODA
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2021 J jnl
On Communication Complexity of Fixed Point Computation.
ACM Trans. Economics and Comput.
Anat Ganor, Karthik C. S., Dömötör Pálvölgyi
2021 J jnl
On Complexity of 1-Center in Various Metrics.
CoRR
Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin
2021 — conf
On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes.
SOSA
Karthik C. S., Inbal Livni Navon
2021 J jnl
Parameterized Intractability of Even Set and Shortest Vector Problem.
J. ACM
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
2020 J jnl
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms.
Algorithms
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2020 J jnl
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms.
CoRR
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2020 J jnl
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms.
Electron. Colloquium Comput. Complex.
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2020 J jnl
Deterministic Replacement Path Covering.
CoRR
Karthik C. S., Merav Parter
2020 A conf
Hardness Amplification of Optimization Problems.
ITCS
Elazar Goldenberg, Karthik C. S.
2020 J jnl
On Approximability of Clustering Problems Without Candidate Centers.
CoRR
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
2020 J jnl
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic.
Comb.
Karthik C. S., Pasin Manurangsi
2020 A* conf
On Efficient Low Distortion Ultrametric Embedding.
ICML
Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde
2020 J jnl
On Efficient Low Distortion Ultrametric Embedding.
CoRR
Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde
2020 J jnl
On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes.
CoRR
Karthik C. S., Inbal Livni Navon
2020 J jnl
Toward a General Direct Product Testing Theorem.
ACM Trans. Comput. Theory
Elazar Goldenberg, Karthik C. S.
2019 J jnl
Hardness Amplification of Optimization Problems.
CoRR
Elazar Goldenberg, Karthik C. S.
2019 J jnl
Hardness Amplification of Optimization Problems.
Electron. Colloquium Comput. Complex.
Elazar Goldenberg, Karthik C. S.
2019 A* conf
Inapproximability of Clustering in Lp Metrics.
FOCS
Vincent Cohen-Addad, Karthik C. S.
2019 A conf
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic.
ITCS
Karthik C. S., Pasin Manurangsi
2019 J jnl
On Communication Complexity of Fixed Point Computation.
CoRR
Anat Ganor, Karthik C. S., Dömötör Pálvölgyi
2019 J jnl
On the Complexity of Closest Pair via Polar-Pair of Point-Sets.
SIAM J. Discret. Math.
Roee David, Karthik C. S., Bundit Laekhanukit
2019 J jnl
On the Parameterized Complexity of Approximating Dominating Set.
J. ACM
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2019 J jnl
Parameterized Intractability of Even Set and Shortest Vector Problem.
CoRR
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
2019 J jnl
Parameterized Intractability of Even Set and Shortest Vector Problem.
Electron. Colloquium Comput. Complex.
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
2019 J jnl
Towards a General Direct Product Testing Theorem.
CoRR
Elazar Goldenberg, Karthik C. S.
2018 J jnl
An Efficient Representation for Filtrations of Simplicial Complexes.
ACM Trans. Algorithms
Jean-Daniel Boissonnat, Karthik C. S.
2018 — conf
Communication Complexity of Correlated Equilibrium with Small Support.
APPROX-RANDOM
Anat Ganor, Karthik C. S.
2018 J jnl
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic.
CoRR
Karthik C. S., Pasin Manurangsi
2018 J jnl
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic.
Electron. Colloquium Comput. Complex.
Karthik C. S., Pasin Manurangsi
2018 A* conf
On the Complexity of Closest Pair via Polar-Pair of Point-Sets.
SoCG
Roee David, Karthik C. S., Bundit Laekhanukit
2018 A* conf
On the parameterized complexity of approximating dominating set.
STOC
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2018 A* conf
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.
ICALP
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
2018 J jnl
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.
CoRR
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
2018 J jnl
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.
Electron. Colloquium Comput. Complex.
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
2018 — conf
Towards a General Direct Product Testing Theorem.
FSTTCS
Elazar Goldenberg, Karthik C. S.
2017 A* conf
An Efficient Representation for Filtrations of Simplicial Complexes.
SODA
Jean-Daniel Boissonnat, Karthik C. S.
2017 J jnl
Building Efficient and Compact Data Structures for Simplicial Complexes.
Algorithmica
Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas
2017 J jnl
Communication Complexity of Correlated Equilibrium in Two-Player Games.
CoRR
Anat Ganor, Karthik C. S.
2017 J jnl
Communication Complexity of Correlated Equilibrium in Two-Player Games.
Electron. Colloquium Comput. Complex.
Anat Ganor, Karthik C. S.
2017 J jnl
Did the train reach its destination: The complexity of finding a witness.
Inf. Process. Lett.
Karthik C. S.
2017 A* conf
Ham Sandwich is Equivalent to Borsuk-Ulam.
SoCG
Karthik C. S., Arpan Saha
2017 J jnl
On the Parameterized Complexity of Approximating Dominating Set.
CoRR
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2017 J jnl
On the Parameterized Complexity of Approximating Dominating Set.
Electron. Colloquium Comput. Complex.
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2016 J jnl
An Efficient Representation for Filtrations of Simplicial Complexes.
CoRR
Jean-Daniel Boissonnat, Karthik C. S.
2016 J jnl
Did the Train Reach its Destination: The Complexity of Finding a Witness.
CoRR
Karthik C. S.
2016 — conf
On the Sensitivity Conjecture for Disjunctive Normal Forms.
FSTTCS
Karthik C. S., Sébastien Tavenas
2016 J jnl
On the Sensitivity Conjecture for Disjunctive Normal Forms.
CoRR
Karthik C. S., Sébastien Tavenas
2016 J jnl
The Curse of Medium Dimension for Geometric Problems in Almost Every Norm.
CoRR
Roee David, Karthik C. S., Bundit Laekhanukit
2015 A* conf
Building Efficient and Compact Data Structures for Simplicial Complexes.
SoCG
Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas
2015 J jnl
Building Efficient and Compact Data Structures for Simplicial Complexes.
CoRR
Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas
2011 J jnl
A Few Equivalences of Wall-Sun-Sun Prime Conjecture
CoRR
Arpan Saha, Karthik C. S.