default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDKarthik C. S. 0001
Person information
- affiliation: Rutgers University New Brunswick, USA
- affiliation (former): New York University, New York City, NY, USA
- affiliation (former): Tel Aviv University, Israel
- affiliation (PhD 2019): Weizmann Institute of Science, Rehovot, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Journal Articles
- 2024
[j13]Surya Teja Gavva, Karthik C. S.
, Sharath Punna:
Clustering categorical data: Soft rounding k-modes. Inf. Comput. 296: 105115 (2024)- [j12]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): 337-347 (2024) - [j11]Karthik C. S., Merav Parter:
Deterministic Replacement Path Covering. ACM Trans. Algorithms 20(4): 34:1-34:35 (2024) - 2021
- [j10]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): 16:1-16:40 (2021) - [j9]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): 25:1-25:27 (2021) - 2020
- [j8]Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi:
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms 13(6): 146 (2020) - [j7]Karthik C. S., Pasin Manurangsi:
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. Comb. 40(4): 539-573 (2020) - [j6]Elazar Goldenberg, Karthik C. S.:
Toward a General Direct Product Testing Theorem. ACM Trans. Comput. Theory 12(1): 7:1-7:18 (2020) - 2019
- [j5]Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi:
On the Parameterized Complexity of Approximating Dominating Set. J. ACM 66(5): 33:1-33:38 (2019) - [j4]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): 509-527 (2019) - 2018
- [j3]Jean-Daniel Boissonnat, Karthik C. S.:
An Efficient Representation for Filtrations of Simplicial Complexes. ACM Trans. Algorithms 14(4): 44:1-44:21 (2018) - 2017
- [j2]Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas:
Building Efficient and Compact Data Structures for Simplicial Complexes. Algorithmica 79(2): 530-567 (2017) - [j1]Karthik C. S.:
Did the train reach its destination: The complexity of finding a witness. Inf. Process. Lett. 121: 17-21 (2017)
Conference and Workshop Papers
- 2024
- [c27]Enver Aman, Karthik C. S., Sharath Punna:
On Connections Between k-Coloring and Euclidean k-Means. ESA 2024: 9:1-9:18 - [c26]Elazar Goldenberg, Mursalin Habib, Karthik C. S.:
Explicit Good Codes Approaching Distance 1 in Ulam Metric. ISIT 2024: 133-138 - [c25]Karthik C. S., Euiwoong Lee, Pasin Manurangsi:
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP. IPEC 2024: 6:1-6:18 - [c24]Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.:
On Approximability of Steiner Tree in ℓp-metrics. SODA 2024: 1669-1703 - [c23]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: 383-395 - 2023
- [c22]Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin:
On Complexity of 1-Center in Various Metrics. APPROX/RANDOM 2023: 1:1-1:19 - [c21]Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier:
Can You Solve Closest String Faster Than Exhaustive Search? ESA 2023: 3:1-3:17 - 2022
- [c20]Karthik C. S., Subhash Khot:
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. CCC 2022: 6:1-6:21 - [c19]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: 222-239 - [c18]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics. SODA 2022: 1493-1530 - 2021
- [c17]Boris Bukh, Karthik C. S., Bhargav Narayanan:
Applications of Random Algebraic Constructions to Hardness of Approximation. FOCS 2021: 237-244 - [c16]Karthik C. S., Merav Parter:
Deterministic Replacement Path Covering. SODA 2021: 704-723 - [c15]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
On Approximability of Clustering Problems Without Candidate Centers. SODA 2021: 2635-2648 - [c14]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: 210-223 - 2020
- [c13]Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde:
On Efficient Low Distortion Ultrametric Embedding. ICML 2020: 2078-2088 - [c12]Elazar Goldenberg, Karthik C. S.:
Hardness Amplification of Optimization Problems. ITCS 2020: 1:1-1:13 - 2019
- [c11]Vincent Cohen-Addad, Karthik C. S.:
Inapproximability of Clustering in Lp Metrics. FOCS 2019: 519-539 - [c10]Karthik C. S., Pasin Manurangsi:
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. ITCS 2019: 17:1-17:16 - 2018
- [c9]Anat Ganor, Karthik C. S.:
Communication Complexity of Correlated Equilibrium with Small Support. APPROX-RANDOM 2018: 12:1-12:16 - [c8]Roee David, Karthik C. S., Bundit Laekhanukit:
On the Complexity of Closest Pair via Polar-Pair of Point-Sets. SoCG 2018: 28:1-28:15 - [c7]Elazar Goldenberg, Karthik C. S.:
Towards a General Direct Product Testing Theorem. FSTTCS 2018: 11:1-11:17 - [c6]Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi:
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. ICALP 2018: 17:1-17:15 - [c5]Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi:
On the parameterized complexity of approximating dominating set. STOC 2018: 1283-1296 - 2017
- [c4]Karthik C. S., Arpan Saha:
Ham Sandwich is Equivalent to Borsuk-Ulam. SoCG 2017: 24:1-24:15 - [c3]Jean-Daniel Boissonnat, Karthik C. S.:
An Efficient Representation for Filtrations of Simplicial Complexes. SODA 2017: 2705-2720 - 2016
- [c2]Karthik C. S., Sébastien Tavenas:
On the Sensitivity Conjecture for Disjunctive Normal Forms. FSTTCS 2016: 15:1-15:15 - 2015
- [c1]Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas:
Building Efficient and Compact Data Structures for Simplicial Complexes. SoCG 2015: 642-656
Informal and Other Publications
- 2024
- [i47]Elazar Goldenberg, Mursalin Habib, Karthik C. S.:
Explicit Good Codes Approaching Distance 1 in Ulam Metric. CoRR abs/2401.17235 (2024) - [i46]Karthik C. S., Saladi Rahul:
Range Longest Increasing Subsequence and its Relatives: Beating Quadratic Barrier and Approaching Optimality. CoRR abs/2404.04795 (2024) - [i45]Enver Aman, Karthik C. S., Sharath Punna:
On connections between k-coloring and Euclidean k-means. CoRR abs/2405.13877 (2024) - [i44]Karthik C. S., Euiwoong Lee, Pasin Manurangsi:
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP. CoRR abs/2407.08917 (2024) - [i43]Karthik C. S., Pasin Manurangsi:
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [i42]Chengyuan Deng, Surya Teja Gavva, Karthik C. S., Parth Patel, Adarsh Srinivasan:
Impossibility of Depth Reduction in Explainable Clustering. CoRR abs/2305.02850 (2023) - [i41]Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier:
Can You Solve Closest String Faster than Exhaustive Search? CoRR abs/2305.16878 (2023) - [i40]Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S.:
On Approximability of Steiner Tree in 𝓁p-metrics. CoRR abs/2306.02189 (2023) - [i39]Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza:
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. CoRR abs/2311.05913 (2023) - [i38]Henry L. Fleischmann, Guillermo A. Gamboa Q., Karthik C. S., Josef Matejka, Jakub Petr:
On Steiner Trees of the Regular Simplex. CoRR abs/2312.01252 (2023) - [i37]Henry L. Fleischmann, Kyrylo Karlov, Karthik C. S., Ashwin Padaki, Stepan Zharkov:
Inapproximability of Maximum Diameter Clustering for Few Clusters. CoRR abs/2312.02097 (2023) - [i36]Karthik C. S., Pasin Manurangsi:
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. CoRR abs/2312.17140 (2023) - [i35]Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, Meirav Zehavi, Martin G. Herold:
Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291). Dagstuhl Reports 13(7): 96-107 (2023) - 2022
- [i34]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 abs/2202.10028 (2022) - [i33]Surya Teja Gavva, Karthik C. S., Sharath Punna:
Clustering Categorical Data: Soft Rounding k-modes. CoRR abs/2210.09640 (2022) - 2021
- [i32]Boris Bukh, Karthik C. S., Bhargav Narayanan:
Applications of Random Algebraic Constructions to Hardness of Approximation. CoRR abs/2111.05518 (2021) - [i31]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics. CoRR abs/2111.10912 (2021) - [i30]Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin:
On Complexity of 1-Center in Various Metrics. CoRR abs/2112.03222 (2021) - [i29]Karthik C. S., Subhash Khot:
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. CoRR abs/2112.03983 (2021) - [i28]Boris Bukh, Karthik C. S., Bhargav Narayanan:
Applications of Random Algebraic Constructions to Hardness of Approximation. Electron. Colloquium Comput. Complex. TR21 (2021) - [i27]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. TR21 (2021) - 2020
- [i26]Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi:
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. CoRR abs/2006.04411 (2020) - [i25]Karthik C. S., Merav Parter:
Deterministic Replacement Path Covering. CoRR abs/2008.05421 (2020) - [i24]Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde:
On Efficient Low Distortion Ultrametric Embedding. CoRR abs/2008.06700 (2020) - [i23]Karthik C. S., Inbal Livni Navon:
On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes. CoRR abs/2009.02778 (2020) - [i22]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
On Approximability of Clustering Problems Without Candidate Centers. CoRR abs/2010.00087 (2020) - [i21]Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi:
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [i20]Elazar Goldenberg, Karthik C. S.:
Towards a General Direct Product Testing Theorem. CoRR abs/1901.06220 (2019) - [i19]Elazar Goldenberg, Karthik C. S.:
Hardness Amplification of Optimization Problems. CoRR abs/1908.10248 (2019) - [i18]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 abs/1909.01986 (2019) - [i17]Anat Ganor, Karthik C. S., Dömötör Pálvölgyi:
On Communication Complexity of Fixed Point Computation. CoRR abs/1909.10958 (2019) - [i16]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. TR19 (2019) - [i15]Elazar Goldenberg, Karthik C. S.:
Hardness Amplification of Optimization Problems. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i14]Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi:
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. CoRR abs/1803.09717 (2018) - [i13]Karthik C. S., Pasin Manurangsi:
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. CoRR abs/1812.00901 (2018) - [i12]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. TR18 (2018) - [i11]Karthik C. S., Pasin Manurangsi:
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [i10]Anat Ganor, Karthik C. S.:
Communication Complexity of Correlated Equilibrium in Two-Player Games. CoRR abs/1704.01104 (2017) - [i9]Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi:
On the Parameterized Complexity of Approximating Dominating Set. CoRR abs/1711.11029 (2017) - [i8]Anat Ganor, Karthik C. S.:
Communication Complexity of Correlated Equilibrium in Two-Player Games. Electron. Colloquium Comput. Complex. TR17 (2017) - [i7]Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi:
On the Parameterized Complexity of Approximating Dominating Set. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i6]Karthik C. S., Sébastien Tavenas:
On the Sensitivity Conjecture for Disjunctive Normal Forms. CoRR abs/1607.05189 (2016) - [i5]Jean-Daniel Boissonnat, Karthik C. S.:
An Efficient Representation for Filtrations of Simplicial Complexes. CoRR abs/1607.08449 (2016) - [i4]Roee David, Karthik C. S., Bundit Laekhanukit:
The Curse of Medium Dimension for Geometric Problems in Almost Every Norm. CoRR abs/1608.03245 (2016) - [i3]Karthik C. S.:
Did the Train Reach its Destination: The Complexity of Finding a Witness. CoRR abs/1609.03840 (2016) - 2015
- [i2]Jean-Daniel Boissonnat, Karthik C. S., Sébastien Tavenas:
Building Efficient and Compact Data Structures for Simplicial Complexes. CoRR abs/1503.07444 (2015) - 2011
- [i1]Arpan Saha, Karthik C. S.:
A Few Equivalences of Wall-Sun-Sun Prime Conjecture. CoRR abs/1102.1636 (2011)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-08 02:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
