Karthik C. S.

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

  1. Truthful Fairness in Decision Making Slides Slides
    Joint work with Vincent Cohen-Addad, Claire Mathieu, and Namrata.
  2. Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p-metrics Slides
    Joint work with Vincent Cohen-Addad and Euiwoong Lee.
  3. Deterministic Replacement Path Covering
    Joint work with Merav Parter.
    SODA 2021.
  4. On Approximability of Clustering Problems Without Candidate Centers
    Joint work with Vincent Cohen-Addad and Euiwoong Lee.
    SODA 2021.
  5. On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes Slides Video
    Joint work with Inbal Livni Navon.
    SOSA 2021.
  6. 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.
    To appear in Journal of the ACM (JACM).
    Preliminary version with Arnab Bhattacharyya, Suprovat Ghoshal, and Pasin Manurangsi appeared in ICALP 2018.
  7. On Efficient Low Distortion Ultrametric Embedding Slides
    Joint work with Vincent Cohen-Addad and Guillaume Lagarde.
    ICML 2020.
  8. On Communication Complexity of Fixed Point Computation
    Joint work with Anat Ganor and Dömötör Pálvölgyi.
    To appear in ACM Transactions on Economics and Computation (TEAC).
  9. 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.
  10. Hardness Amplification of Optimization Problems Slides
    Joint work with Elazar Goldenberg.
    ITCS 2020.
  11. Inapproximability of Clustering in L_p-metrics Slides Video
    Joint work with Vincent Cohen-Addad.
    FOCS 2019.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. Communication Complexity of Correlated Equilibrium in Two-Player Games
    Joint work with Anat Ganor.
  17. Ham Sandwich is Equivalent to Borsuk-Ulam Slides
    Joint work with Arpan Saha.
    SoCG 2017.
  18. 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.
  19. Did the Train Reach its Destination: The Complexity of Finding a Witness
    Information Processing Letters (IPL), 121(5): 17-21, 2017.
  20. On the Sensitivity Conjecture for Disjunctive Normal Forms Slides
    Joint work with Sébastien Tavenas.
    FSTTCS 2016.
  21. 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.