All reports by Author Pasin Manurangsi:

__
TR24-007
| 25th December 2023
__

Karthik C. S., Pasin Manurangsi#### On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

Revisions: 1

__
TR20-086
| 5th June 2020
__

Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi#### A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

__
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

__
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

The field of combinatorial reconfiguration studies search problems with a focus on transforming one feasible solution into another.

Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some $\varepsilon>0$ such that given as input a $k$-CSP instance (for some constant $k$) over ... more >>>

Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi

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 >>>Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

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

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