Остановите войну!
for scientists:
default search action
Karthik C. S.
- > Home > Persons > Karthik C. S.
Publications
- 2024
- [j11]Surya Teja Gavva, Karthik C. S., Sharath Punna:
Clustering categorical data: Soft rounding k-modes. Inf. Comput. 296: 105115 (2024) - [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 - [i44]Elazar Goldenberg, Mursalin Habib, Karthik C. S.:
Explicit Good Codes Approaching Distance 1 in Ulam Metric. CoRR abs/2401.17235 (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: TR24-007 (2024) - 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 - [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 Herold:
Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291). Dagstuhl Reports 13(7): 96-107 (2023) - 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 - [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
- [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) - [c15]Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee:
On Approximability of Clustering Problems Without Candidate Centers. SODA 2021: 2635-2648 - [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) - [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
- [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) - [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 - [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) - [i24]Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde:
On Efficient Low Distortion Ultrametric Embedding. CoRR abs/2008.06700 (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
- [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) - [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 - [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) - [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
- [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 - [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
- [i9]Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi:
On the Parameterized Complexity of Approximating Dominating Set. CoRR abs/1711.11029 (2017) - [i7]Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi:
On the Parameterized Complexity of Approximating Dominating Set. Electron. Colloquium Comput. Complex. TR17 (2017) - 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)
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-04-25 05:43 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint