Karthik C. S.

NOTE: If you are preparing a bibtex entry to cite any of the papers that I have coauthored, then please write my name as {Karthik {C. S.}}. See an example here.




  1. On Complexity of 1-Center in Various Metrics
    Joint work with Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, and Saeed Seddighin.
  2. Obtaining Approximately Optimal and Diverse Solutions via Dispersion
    Joint work with Jie Gao, Mayank Goswami, Meng-Tsung Tsai, Shih-Yu Tsai, and Hao-Tsung Yang.
    LATIN 2022.
  3. Almost Polynomial Factor Inapproximability for Parameterized k-Clique Slides
    Joint work with Subhash Khot.
    CCC 2022.
    Invited to ToC Special Issue for CCC 2022.
  4. Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p-metrics Slides
    Joint work with Vincent Cohen-Addad and Euiwoong Lee.
    SODA 2022.
  5. Applications of Random Algebraic Constructions to Hardness of Approximation Slides Video
    Joint work with Boris Bukh and Bhargav Narayanan.
    FOCS 2021.
    To appear in Israel Journal of Mathematics.
  6. Fairness of Linear Regression in Decision Making Slides Slides
    Joint work with Vincent Cohen-Addad, Surya Teja Gavva, Claire Mathieu, and Namrata.
  7. Deterministic Replacement Path Covering
    Joint work with Merav Parter.
    SODA 2021.
  8. On Approximability of Clustering Problems Without Candidate Centers
    Joint work with Vincent Cohen-Addad and Euiwoong Lee.
    SODA 2021.
  9. On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes
    Joint work with Inbal Livni Navon.
    SOSA 2021.
  10. On Communication Complexity of Fixed Point Computation
    Joint work with Anat Ganor and Dömötör Pálvölgyi.
    ACM Transactions on Economics and Computation (TEAC), 9(4): 25:1-25:27, 2021.
  11. Parameterized Intractability of Even Set and Shortest Vector Problem
    Joint work with Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Bingkai Lin, Pasin Manurangsi, and Dániel Marx.
    Journal of the ACM (JACM), 68(3): 16:1-16:40, 2021.
    Preliminary version with Arnab Bhattacharyya, Suprovat Ghoshal, and Pasin Manurangsi appeared in ICALP 2018.
  12. On Efficient Low Distortion Ultrametric Embedding Slides
    Joint work with Vincent Cohen-Addad and Guillaume Lagarde.
    ICML 2020.
  13. A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
    Joint work with Andreas Emil Feldmann, Euiwoong Lee, and Pasin Manurangsi.
    Algorithms, 13(6), 146, 2020.
  14. Hardness Amplification of Optimization Problems Slides
    Joint work with Elazar Goldenberg.
    ITCS 2020.
  15. Inapproximability of Clustering in L_p-metrics Slides Video
    Joint work with Vincent Cohen-Addad.
    FOCS 2019.
  16. On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic Slides
    Joint work with Pasin Manurangsi.
    ITCS 2019.
    Combinatorica, 40(4): 539-573, 2020.
  17. On the Parameterized Complexity of Approximating Dominating Set Slides
    Joint work with Bundit Laekhanukit and Pasin Manurangsi.
    STOC 2018.
    Journal of the ACM (JACM), 66(5): 33:1-33:38, 2019.
    Invited to SICOMP Special Issue for STOC 2018 (regretfully declined ).
    Invited to HALG 2019.
    Here is a brief desription of the result in FPT News: The Parameterized Complexity Newsletter.
  18. On the Complexity of Closest Pair via Polar-Pair of Point-Sets Slides
    Joint work with Roee David and Bundit Laekhanukit.
    SoCG 2018.
    SIAM Journal on Discrete Mathematics (SIDMA), 33(1): 509-527, 2019.
  19. Towards a General Direct Product Testing Theorem
    Joint work with Elazar Goldenberg.
    FSTTCS 2018.
    ACM Transactions on Computation Theory (TOCT), 12(1): 7:1-7:18, 2020.
  20. Communication Complexity of Correlated Equilibrium in Two-Player Games
    Joint work with Anat Ganor.
    APPROX-RANDOM 2018.
  21. Ham Sandwich is Equivalent to Borsuk-Ulam Slides
    Joint work with Arpan Saha.
    SoCG 2017.
  22. An Efficient Representation for Filtrations of Simplicial Complexes Slides
    Joint work with Jean-Daniel Boissonnat.
    SODA 2017.
    ACM Transactions on Algorithms (TALG), 14(4): 44:1-44:21, 2018.
  23. Did the Train Reach its Destination: The Complexity of Finding a Witness
    Information Processing Letters (IPL), 121(5): 17-21, 2017.
  24. On the Sensitivity Conjecture for Disjunctive Normal Forms Slides
    Joint work with Sébastien Tavenas.
    FSTTCS 2016.
  25. Building Efficient and Compact Data Structures for Simplicial Complexes Slides
    Joint work with Jean-Daniel Boissonnat and Sébastien Tavenas.
    SoCG 2015.
    Algorithmica, 79(2): 530-567, 2017.