7 papers
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on variables and alphab…
Explicit Good Codes Approaching Distance 1 in Ulam Metric
Elazar Goldenberg, Mursalin Habib, Karthik C. S
The Ulam distance of two permutations on is minus the length of their longest common subsequence. In this paper, we show that for every , there exists some…
Deterministic Replacement Path Covering
Karthik C. S., Merav Parter
In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph , a vertex pair $(s,t)…
Parameterized Intractability of Even Set and Shortest Vector Problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri +5
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 $\m…
On Communication Complexity of Fixed Point Computation
Anat Ganor, Karthik C. S., Dömötör Pálvölgyi
Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study…
On the Parameterized Complexity of Approximating Dominating Set
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
We study the parameterized complexity of approximating the -Dominating Set (DomSet) problem where an integer and a graph on vertices are given as input, and the goal…
An Efficient Representation for Filtrations of Simplicial Complexes
Jean-Daniel Boissonnat, Karthik C. S.
A filtration over a simplicial complex is an ordering of the simplices of such that all prefixes in the ordering are subcomplexes of . Filtrations are at the core of Per…