Karthik C. S.

IMPORTANT: Please use the bibtex entry from DBLP to cite any of the papers that I have coauthored.




  1. On Efficient Low Distortion Ultrametric Embedding Slides
    Joint work with Vincent Cohen-Addad and Guillaume Lagarde.
    ICML 2020.
  2. 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. (By invitation to special issue "New Frontiers in Parameterized Complexity and Algorithms".)
  3. On Approximability of k-means, k-median, and k-minsum Clustering Slides
    Joint work with Vincent Cohen-Addad and Euiwoong Lee.
  4. Hardness Amplification of Optimization Problems Slides
    Joint work with Elazar Goldenberg.
    ITCS 2020.
  5. On Communication Complexity of Fixed Point Computation
    Joint work with Anat Ganor and Dömötör Pálvölgyi.
  6. Inapproximability of Clustering in L_p-metrics Slides Video
    Joint work with Vincent Cohen-Addad.
    FOCS 2019.
  7. On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic Slides
    Joint work with Pasin Manurangsi.
    ITCS 2019.
    To appear in Combinatorica.
  8. 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.
  9. Communication Complexity of Correlated Equilibrium in Two-Player Games
    Joint work with Anat Ganor.
    APPROX-RANDOM 2018.
  10. 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.
    Preliminary version with Arnab Bhattacharyya, Suprovat Ghoshal, and Pasin Manurangsi appeared in ICALP 2018.
  11. 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.
  12. 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.
  13. Ham Sandwich is Equivalent to Borsuk-Ulam Slides
    Joint work with Arpan Saha.
    SoCG 2017.
  14. 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.
  15. Did the Train Reach its Destination: The Complexity of Finding a Witness
    Information Processing Letters (IPL), 121(5): 17-21, 2017.
  16. On the Sensitivity Conjecture for Disjunctive Normal Forms Slides
    Joint work with Sébastien Tavenas.
    FSTTCS 2016.
  17. 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.