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

__
TR18-093
| 10th May 2018
__

Irit Dinur, Pasin Manurangsi#### ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

__
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

__
TR17-186
| 29th November 2017
__

Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi#### On the Parameterized Complexity of Approximating Dominating Set

Revisions: 1

__
TR16-195
| 19th November 2016
__

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

Revisions: 1

Karthik C. S., Pasin Manurangsi

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 >>>

Irit Dinur, Pasin Manurangsi

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 >>>

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

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 >>>

Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

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 >>>

Pasin Manurangsi

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 >>>