Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Karthik C. S.:

TR21-177 | 22nd November 2021
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics

k-median and k-means are the two most popular objectives for clustering algorithms. Despite intensive effort, a good understanding of the approximability of these objectives, particularly in $\ell_p$-metrics, remains a major open problem. In this paper, we significantly improve upon the hardness of approximation factors known in literature for these objectives ... more >>>

TR21-156 | 10th November 2021
Boris Bukh, Karthik C. S., Bhargav Narayanan

Applications of Random Algebraic Constructions to Hardness of Approximation

In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural.

(*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in ... more >>>

TR20-086 | 5th June 2020
Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

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.

more >>>

TR19-125 | 27th August 2019
Elazar Goldenberg, Karthik C. S.

Hardness Amplification of Optimization Problems

In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products.

We say that an optimization problem $\Pi$ is direct product feasible if it is possible to efficiently aggregate any $k$ instances of $\Pi$ and form one large instance ... more >>>

TR19-115 | 4th September 2019
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

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb{F}_2$, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether ... more >>>

TR18-210 | 30th November 2018
Karthik C. S., Pasin Manurangsi

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

Given a set of $n$ points in $\mathbb R^d$, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the $\ell_p$-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when ... more >>>

TR18-057 | 26th March 2018
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$. Here, $k$ ... more >>>

TR17-186 | 29th November 2017
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

On the Parameterized Complexity of Approximating Dominating Set

Revisions: 1

We study the parameterized complexity of approximating the $k$-Dominating Set (domset) problem where an integer $k$ and a graph $G$ on $n$ vertices are given as input, and the goal is to find a dominating set of size at most $F(k) \cdot k$ whenever the graph $G$ has a dominating ... more >>>

TR17-061 | 3rd April 2017
Anat Ganor, Karthik C. S.

Communication Complexity of Correlated Equilibrium in Two-Player Games

We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player $N \times N$ game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is $\Omega(N)$. For ... more >>>

ISSN 1433-8092 | Imprint