KSKarthik C. S.
Karthik C. S.
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Karthik C. S. has a total of 57 co-authors. Here are the top co-authors by number of shared publications:
- Pasin Manurangsi
Google Research, Mountain View, CA, USA
7 shared publications - Elazar Goldenberg
The Academic College of Tel Aviv-Yaffo
4 shared publications - Sébastien Tavenas
Microsoft Research India
3 shared publications - Amir Abboud
Weizmann Institute of Science
2 shared publications - Anat Ganor
Tel-Aviv University Israel
2 shared publications - Bundit Laekhanukit
Weizmann Institute of Science Israel
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 330-341
Fine-Grained Complexity of Continuous Euclidean k-Center
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 330-341
Open AccessFine-Grained Complexity of Continuous Euclidean k-Center
- Open Access
- 4 March 2026
- Published by Elsevier in Information and Computation
- Vol. 310
Impossibility of depth reduction in explainable clustering
- 4 March 2026
- Published by Elsevier in Information and Computation
- Vol. 310
Open AccessImpossibility of depth reduction in explainable clustering
- 13 August 2025
- Published by Springer Nature in Algorithmica
- Vol. 87 (12) , 1711-1731
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
- 13 August 2025
- Published by Springer Nature in Algorithmica
- Vol. 87 (12) , 1711-1731
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2118-2129
Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2118-2129
Open AccessNear Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity
- 2 May 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (7) , 5082-5088
Explicit Good Codes Approaching Distance 1 in Ulam Metric
The Ulam distance between two permutations on$[n]$ is n minus the length of their longest common subsequence. In this paper, we show that for every$\rho \gt 0$ , there exists some$\epsilon \gt 0$ , and an infinite set$\Gamma \subseteq \mathbb {N}$ , such that for all$n\in \Gamma $ , there is an explicit set$C_{n}$ of$(n!)^{\epsilon }$ many permutations on$[n]$ , such that every pair of permutations in$C_{n}$ has pairwise Ulam distance at least$(1-\rho)\cdot n$ . Moreover, we can compute the$i^{\text {th}}$ permutation in$C_{n}$ in$\mathrm {poly}(n)$ time and can also decode in$\mathrm {poly}(n)$ time, a permutation$\pi $ on$[n]$ to its closest permutation$\pi ^{*}$ in$C_{n}$ , if the Ulam distance of$\pi $ and$\pi ^{*}$ is less than$ \frac {(1-\rho)\cdot n}{4} $ . Previously, it was implicitly known by combining works of Goldreich and Wigderson [Israel Journal of Mathematics’23] and Farnoud, Skachek, and Milenkovic [IEEE Transactions on Information Theory’13] in a black-box manner, that it is possible to explicitly construct$(n!)^{\Omega (1)}$ many permutations on$[n]$ , such that every pair of them have pairwise Ulam distance at least$\frac {n}{6}\cdot (1-\rho)$ , for any$\rho \gt 0$ , and the bound on the distance can be improved to$\frac {n}{4}\cdot (1-\rho)$ if the construction of Goldreich and Wigderson is directly analyzed in the Ulam metric.- 2 May 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (7) , 5082-5088
Explicit Good Codes Approaching Distance 1 in Ulam Metric
The Ulam distance between two permutations on$[n]$ is n minus the length of their longest common subsequence. In this paper, we show that for every$\rho \gt 0$ , there exists some$\epsilon \gt 0$ , and an infinite set$\Gamma \subseteq \mathbb {N}$ , such that for all$n\in \Gamma $ , there is an explicit set$C_{n}$ of$(n!)^{\epsilon }$ many permutations on$[n]$ , such that every pair of permutations in$C_{n}$ has pairwise Ulam distance at least$(1-\rho)\cdot n$ . Moreover, we can compute the$i^{\text {th}}$ permutation in$C_{n}$ in$\mathrm {poly}(n)$ time and can also decode in$\mathrm {poly}(n)$ time, a permutation$\pi $ on$[n]$ to its closest permutation$\pi ^{*}$ in$C_{n}$ , if the Ulam distance of$\pi $ and$\pi ^{*}$ is less than$ \frac {(1-\rho)\cdot n}{4} $ . Previously, it was implicitly known by combining works of Goldreich and Wigderson [Israel Journal of Mathematics’23] and Farnoud, Skachek, and Milenkovic [IEEE Transactions on Information Theory’13] in a black-box manner, that it is possible to explicitly construct$(n!)^{\Omega (1)}$ many permutations on$[n]$ , such that every pair of them have pairwise Ulam distance at least$\frac {n}{6}\cdot (1-\rho)$ , for any$\rho \gt 0$ , and the bound on the distance can be improved to$\frac {n}{4}\cdot (1-\rho)$ if the construction of Goldreich and Wigderson is directly analyzed in the Ulam metric.- Open Access
Hardness of Median and Center in the Ulam Metric
The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamental rank aggregation tasks under the well-studied Ulam metric: computing a median permutation (which minimizes the sum of Ulam distances to X) and computing a center permutation (which minimizes the maximum Ulam distance to X) in two settings. $\bullet$ Continuous Setting: In the continuous setting, the median/center is allowed to be any permutation. It is known that computing a center in the Ulam metric is NP-hard and we add to this by showing that computing a median is NP-hard as well via a simple reduction from the Max-Cut problem. While this result may not be unexpected, it had remained elusive until now and confirms a speculation by Chakraborty, Das, and Krauthgamer [SODA '21]. $\bullet$ Discrete Setting: In the discrete setting, the median/center must be a permutation from the input set. We fully resolve the fine-grained complexity of the discrete median and discrete center problems under the Ulam metric, proving that the naive $\widetilde{O}(n^2 L)$-time algorithm (where L is the length of the permutation) is conditionally optimal. This resolves an open problem raised by Abboud, Bateni, Cohen-Addad, Karthik C. S., and Seddighin [APPROX '23]. Our reductions are inspired by the known fine-grained lower bounds for similarity measures, but we face and overcome several new highly technical challenges.Open AccessHardness of Median and Center in the Ulam Metric
The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamental rank aggregation tasks under the well-studied Ulam metric: computing a median permutation (which minimizes the sum of Ulam distances to X) and computing a center permutation (which minimizes the maximum Ulam distance to X) in two settings. $\bullet$ Continuous Setting: In the continuous setting, the median/center is allowed to be any permutation. It is known that computing a center in the Ulam metric is NP-hard and we add to this by showing that computing a median is NP-hard as well via a simple reduction from the Max-Cut problem. While this result may not be unexpected, it had remained elusive until now and confirms a speculation by Chakraborty, Das, and Krauthgamer [SODA '21]. $\bullet$ Discrete Setting: In the discrete setting, the median/center must be a permutation from the input set. We fully resolve the fine-grained complexity of the discrete median and discrete center problems under the Ulam metric, proving that the naive $\widetilde{O}(n^2 L)$-time algorithm (where L is the length of the permutation) is conditionally optimal. This resolves an open problem raised by Abboud, Bateni, Cohen-Addad, Karthik C. S., and Seddighin [APPROX '23]. Our reductions are inspired by the known fine-grained lower bounds for similarity measures, but we face and overcome several new highly technical challenges. - 17 February 2025
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 268 (1) , 1-43
Applications of random algebraic constructions to hardness of approximation
- 17 February 2025
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 268 (1) , 1-43
Applications of random algebraic constructions to hardness of approximation
- Open Access
- 20 January 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
On Approximability of Steiner Tree in $\ell_p$-metrics
In the Continuous Steiner Tree problem (CST), we are given as input a set of points (called terminals) in a metric space and ask for the minimum-cost tree connecting them. Additional points (called Steiner points) from the metric space can be introduced as nodes in the solution. In the Discrete Steiner Tree problem (DST), we are given in addition to the terminals, a set of facilities, and any solution tree connecting the terminals can only contain the Steiner points from this set of facilities. Trevisan [SICOMP'00] showed that CST and DST are APX-hard when the input lies in the $\ell_1$-metric (and Hamming metric). Chleb\'ik and Chleb\'ikov\'a [TCS'08] showed that DST is NP-hard to approximate to factor of $96/95\approx 1.01$ in the graph metric (and consequently $\ell_\infty$-metric). Prior to this work, it was unclear if CST and DST are APX-hard in essentially every other popular metric. In this work, we prove that DST is APX-hard in every $\ell_p$-metric. We also prove that CST is APX-hard in the $\ell_{\infty}$-metric. Finally, we relate CST and DST, showing a general reduction from CST to DST in $\ell_p$-metrics.Comment: Abstract shortened. Journal version for TheoretiCS- 20 January 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Open AccessOn Approximability of Steiner Tree in $\ell_p$-metrics
In the Continuous Steiner Tree problem (CST), we are given as input a set of points (called terminals) in a metric space and ask for the minimum-cost tree connecting them. Additional points (called Steiner points) from the metric space can be introduced as nodes in the solution. In the Discrete Steiner Tree problem (DST), we are given in addition to the terminals, a set of facilities, and any solution tree connecting the terminals can only contain the Steiner points from this set of facilities. Trevisan [SICOMP'00] showed that CST and DST are APX-hard when the input lies in the $\ell_1$-metric (and Hamming metric). Chleb\'ik and Chleb\'ikov\'a [TCS'08] showed that DST is NP-hard to approximate to factor of $96/95\approx 1.01$ in the graph metric (and consequently $\ell_\infty$-metric). Prior to this work, it was unclear if CST and DST are APX-hard in essentially every other popular metric. In this work, we prove that DST is APX-hard in every $\ell_p$-metric. We also prove that CST is APX-hard in the $\ell_{\infty}$-metric. Finally, we relate CST and DST, showing a general reduction from CST to DST in $\ell_p$-metrics.Comment: Abstract shortened. Journal version for TheoretiCS - Open Access
- 5 August 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (4) , 1-35
Deterministic Replacement Path Covering
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 \(G\) , a vertex pair \((s,t)\in V(G)\times V(G)\) , and a set of edge faults \(F\subseteq E(G)\) , a replacement path \(P(s,t,F)\) is an \(s\) - \(t\) shortest path in \(G\setminus F\) . For integer parameters \(L,f\) , a replacement path covering ( \(\mathsf{RPC}\) ) is a collection of subgraphs of \(G\) , denoted by \(\mathcal{G}_{L,f}=\{G_{1},\ldots,G_{r}\}\) , such that for every set \(F\) of at most \(f\) faults (i.e., \(|F|\leq f\) ) and every replacement path \(P(s,t,F)\) of at most \(L\) edges, there exists a subgraph \(G_{i}\in\mathcal{G}_{L,f}\) that contains all the edges of \(P\) and does not contain any of the edges of \(F\) . The covering value of the \(\mathsf{RPC}\) \(\mathcal{G}_{L,f}\) is then defined to be the number of subgraphs in \(\mathcal{G}_{L,f}\) . In the randomized setting, it is easy to build an \((L,f)\) - \(\mathsf{RPC}\) with covering value of \(O(\max\{L,f\}^{\min\{L,f\}}\cdot\min\{L,f\}\cdot \log n)\) , but to this date, there is no efficient deterministic algorithm with matching bounds. As noted recently by Alon et al. (ICALP 2019), this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following: — There exist efficient deterministic constructions of \((L,f)\) - \(\mathsf{RPC}\) s whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call HM hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed–Solomon codes and Algebraic-Geometric codes. — For every \(L,f\) , and \(n\) , there exists an \(n\) -vertex graph \(G\) whose \((L,f)\) - \(\mathsf{RPC}\) covering value is \(\Omega(L^{f})\) . This lower bound is obtained by exploiting connections to the problem of designing sparse fault-tolerant breadth first search (BFS) structures. An application of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon et al. (ICALP 2019). Additionally, we show a derandomization of the randomized construction of vertex fault-tolerant spanners by Dinitz and Krauthgamer (PODC 2011) and Braunschvig et al. (Theor. Comput. Sci., 2015). The time complexity and the size bounds of the output spanners nearly match the randomized counterparts.- 5 August 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (4) , 1-35
Open AccessDeterministic Replacement Path Covering
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 \(G\) , a vertex pair \((s,t)\in V(G)\times V(G)\) , and a set of edge faults \(F\subseteq E(G)\) , a replacement path \(P(s,t,F)\) is an \(s\) - \(t\) shortest path in \(G\setminus F\) . For integer parameters \(L,f\) , a replacement path covering ( \(\mathsf{RPC}\) ) is a collection of subgraphs of \(G\) , denoted by \(\mathcal{G}_{L,f}=\{G_{1},\ldots,G_{r}\}\) , such that for every set \(F\) of at most \(f\) faults (i.e., \(|F|\leq f\) ) and every replacement path \(P(s,t,F)\) of at most \(L\) edges, there exists a subgraph \(G_{i}\in\mathcal{G}_{L,f}\) that contains all the edges of \(P\) and does not contain any of the edges of \(F\) . The covering value of the \(\mathsf{RPC}\) \(\mathcal{G}_{L,f}\) is then defined to be the number of subgraphs in \(\mathcal{G}_{L,f}\) . In the randomized setting, it is easy to build an \((L,f)\) - \(\mathsf{RPC}\) with covering value of \(O(\max\{L,f\}^{\min\{L,f\}}\cdot\min\{L,f\}\cdot \log n)\) , but to this date, there is no efficient deterministic algorithm with matching bounds. As noted recently by Alon et al. (ICALP 2019), this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following: — There exist efficient deterministic constructions of \((L,f)\) - \(\mathsf{RPC}\) s whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call HM hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed–Solomon codes and Algebraic-Geometric codes. — For every \(L,f\) , and \(n\) , there exists an \(n\) -vertex graph \(G\) whose \((L,f)\) - \(\mathsf{RPC}\) covering value is \(\Omega(L^{f})\) . This lower bound is obtained by exploiting connections to the problem of designing sparse fault-tolerant breadth first search (BFS) structures. An application of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon et al. (ICALP 2019). Additionally, we show a derandomization of the randomized construction of vertex fault-tolerant spanners by Dinitz and Krauthgamer (PODC 2011) and Braunschvig et al. (Theor. Comput. Sci., 2015). The time complexity and the size bounds of the output spanners nearly match the randomized counterparts. - Open Access
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on $k$ variables and alphabet size $n$, it is W[1]-hard parameterized by $k$ to distinguish if the input is perfectly satisfiable or if every assignment to the input violates 1% of the constraints. An important implication of PIH is that it yields the tight parameterized inapproximability of the $k$-maxcoverage problem. In the $k$-maxcoverage problem, we are given as input a set system, a threshold $τ>0$, and a parameter $k$ and the goal is to determine if there exist $k$ sets in the input whose union is at least $τ$ fraction of the entire universe. PIH is known to imply that it is W[1]-hard parameterized by $k$ to distinguish if there are $k$ input sets whose union is at least $τ$ fraction of the universe or if the union of every $k$ input sets is not much larger than $τ\cdot (1-\frac{1}{e})$ fraction of the universe. In this work we present a gap preserving FPT reduction (in the reverse direction) from the $k$-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating the $k$-maxcoverage problem to some constant factor is W[1]-hard implies PIH. In addition, we present a gap preserving FPT reduction from the $k$-median problem (in general metrics) to the $k$-maxcoverage problem, further highlighting the power of gap preserving FPT reductions over classical gap preserving polynomial time reductions.Open AccessOn Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on $k$ variables and alphabet size $n$, it is W[1]-hard parameterized by $k$ to distinguish if the input is perfectly satisfiable or if every assignment to the input violates 1% of the constraints. An important implication of PIH is that it yields the tight parameterized inapproximability of the $k$-maxcoverage problem. In the $k$-maxcoverage problem, we are given as input a set system, a threshold $τ>0$, and a parameter $k$ and the goal is to determine if there exist $k$ sets in the input whose union is at least $τ$ fraction of the entire universe. PIH is known to imply that it is W[1]-hard parameterized by $k$ to distinguish if there are $k$ input sets whose union is at least $τ$ fraction of the universe or if the union of every $k$ input sets is not much larger than $τ\cdot (1-\frac{1}{e})$ fraction of the universe. In this work we present a gap preserving FPT reduction (in the reverse direction) from the $k$-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating the $k$-maxcoverage problem to some constant factor is W[1]-hard implies PIH. In addition, we present a gap preserving FPT reduction from the $k$-median problem (in general metrics) to the $k$-maxcoverage problem, further highlighting the power of gap preserving FPT reductions over classical gap preserving polynomial time reductions.