Karthik C. S.

Orcid: 0000-0001-9105-364X

Affiliations:
  • Rutgers University New Brunswick, USA
  • New York University, New York City, NY, USA (former)
  • Tel Aviv University, Israel (former)
  • Weizmann Institute of Science, Rehovot, Israel (PhD 2019)


According to our database1, Karthik C. S. authored at least 42 papers between 2011 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Clustering categorical data: Soft rounding <i>k</i>-modes.
Inf. Comput., January, 2024

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.
Electron. Colloquium Comput. Complex., 2024

Explicit Good Codes Approaching Distance 1 in Ulam Metric.
CoRR, 2024

2023
Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291).
Dagstuhl Reports, 2023

Inapproximability of Maximum Diameter Clustering for Few Clusters.
CoRR, 2023

On Steiner Trees of the Regular Simplex.
CoRR, 2023

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof.
CoRR, 2023

On Approximability of Steiner Tree in 𝓁<sub>p</sub>-metrics.
CoRR, 2023

Impossibility of Depth Reduction in Explainable Clustering.
CoRR, 2023

Can You Solve Closest String Faster Than Exhaustive Search?
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

On Complexity of 1-Center in Various Metrics.
Proceedings of the Approximation, 2023

2022
Clustering Categorical Data: Soft Rounding k-modes.
CoRR, 2022

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓ<sub>p</sub>-metrics.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Obtaining Approximately Optimal and Diverse Solutions via Dispersion.
Proceedings of the LATIN 2022: Theoretical Informatics, 2022

Almost Polynomial Factor Inapproximability for Parameterized k-Clique.
Proceedings of the 37th Computational Complexity Conference, 2022

2021
On Communication Complexity of Fixed Point Computation.
ACM Trans. Economics and Comput., 2021

Parameterized Intractability of Even Set and Shortest Vector Problem.
J. ACM, 2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics.
Electron. Colloquium Comput. Complex., 2021

Applications of Random Algebraic Constructions to Hardness of Approximation.
Electron. Colloquium Comput. Complex., 2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics.
CoRR, 2021

On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes.
Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Deterministic Replacement Path Covering.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On Approximability of Clustering Problems Without Candidate Centers.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020
Toward a General Direct Product Testing Theorem.
ACM Trans. Comput. Theory, 2020

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms.
Electron. Colloquium Comput. Complex., 2020

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic.
Comb., 2020

On Efficient Low Distortion Ultrametric Embedding.
Proceedings of the 37th International Conference on Machine Learning, 2020

2019
On the Complexity of Closest Pair via Polar-Pair of Point-Sets.
SIAM J. Discret. Math., 2019

On the Parameterized Complexity of Approximating Dominating Set.
J. ACM, 2019

Hardness Amplification of Optimization Problems.
Electron. Colloquium Comput. Complex., 2019

Inapproximability of Clustering in Lp Metrics.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
An Efficient Representation for Filtrations of Simplicial Complexes.
ACM Trans. Algorithms, 2018

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.
Electron. Colloquium Comput. Complex., 2018

Towards a General Direct Product Testing Theorem.
Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

Communication Complexity of Correlated Equilibrium with Small Support.
Proceedings of the Approximation, 2018

2017
Did the train reach its destination: The complexity of finding a witness.
Inf. Process. Lett., 2017

Communication Complexity of Correlated Equilibrium in Two-Player Games.
Electron. Colloquium Comput. Complex., 2017

Building Efficient and Compact Data Structures for Simplicial Complexes.
Algorithmica, 2017

Ham Sandwich is Equivalent to Borsuk-Ulam.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016
The Curse of Medium Dimension for Geometric Problems in Almost Every Norm.
CoRR, 2016

On the Sensitivity Conjecture for Disjunctive Normal Forms.
Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

2011
A Few Equivalences of Wall-Sun-Sun Prime Conjecture
CoRR, 2011


  Loading...