Karthik C. S.

Dr. Karthik C. S.


Research Focus & Metrics

Academic Career Length

11Years (2016-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 June 2020 in Algorithms
Verified
Journal Article
Open access
PDF file
AFAndreas Emil Feldmann
Andreas Emil Feldmann
KSKarthik C. S.
Karthik C. S.
ELEuiwoong Lee
Euiwoong Lee
PMPasin Manurangsi
Pasin Manurangsi
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

22 March 2021 in Journal of the ACM
Verified
Journal Article
Open access
ABArnab Bhattacharyya
Arnab Bhattacharyya
ÉBÉdouard Bonnet
Édouard Bonnet
LELászló Egri
László Egri
SGSuprovat Ghoshal
Suprovat Ghoshal
KSKarthik C. S.
Karthik C. S.
DMDániel Marx
Dániel Marx
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix and an integer , determine whether the code generated by has distance at most , or, in other words, whether there is a nonzero vector such that has at most nonzero coordinates. The question of whether -Even Set is fixed parameter tractable (FPT) parameterized by the distance has been repeatedly raised in the literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that -Even Set is W [1]-hard under randomized reductions. We also consider the parameterized -Shortest Vector Problem (SVP) , in which we are given a lattice whose basis vectors are integral and an integer , and the goal is to determine whether the norm of the shortest vector (in the norm for some fixed ) is at most . Similar to -Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any , -SVP is W [1]-hard to approximate (under randomized reductions) to some constant factor.

1 May 2017 in Information Processing Letters
Verified
Journal Article
Closed access
KSKarthik C. S.
Karthik C. S.

8 September 2016 in Algorithmica
Verified
Journal Article
Open access
PDF file
JBJean-Daniel Boissonnat
Jean-Daniel Boissonnat
KSKarthik C. S.
Karthik C. S.
STSébastien Tavenas
Sébastien Tavenas
The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings.

28 April 2020 in Combinatorica
Verified
Journal Article
Closed access
PDF file
KSKarthik C. S.
Karthik C. S.
PMPasin Manurangsi
Pasin Manurangsi

21 August 2018 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PDF file
JBJean-Daniel Boissonnat
Jean-Daniel Boissonnat
KSKarthik C. S.
Karthik C. S.
A filtration over a simplicial complex K is an ordering of the simplices of K such that all prefixes in the ordering are subcomplexes of K . Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. To represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree [Algorithmica’14]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest. This direction has been recently pursued for the case of maintaining simplicial complexes. For instance, Boissonnat et al. [Algorithmica’17] considered storing the simplices that are maximal with respect to inclusion and Attali et al. [IJCGA’12] considered storing the simplices that block the expansion of the complex. Nevertheless, so far there has been no data structure that compactly stores the filtration of a simplicial complex, while also allowing the efficient implementation of basic operations on the complex. In this article, we propose a new data structure called the Critical Simplex Diagram (CSD), which is a variant of the Simplex Array List [Algorithmica’17]. Our data structure allows one to store in a compact way the filtration of a simplicial complex and allows for the efficient implementation of a large range of basic operations. Moreover, we prove that our data structure is essentially optimal with respect to the requisite storage space. Finally, we show that the CSD representation admits fast construction algorithms for Flag complexes and relaxed Delaunay complexes.