Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pasin Manurangsi:

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-093 | 10th May 2018
Irit Dinur, Pasin Manurangsi

ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph $G = (V, E)$, an alphabet set $\Sigma$ and, for each edge $\{u, v\} \in E$, a constraint $C_{uv} \subseteq \Sigma \times \Sigma$, the goal is to find an assignment $\sigma: V ... 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 >>>

TR16-195 | 19th November 2016
Pasin Manurangsi

Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph

Revisions: 1

In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio (Bhaskara et al., ... more >>>

ISSN 1433-8092 | Imprint