Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Hardness of Approximation:
TR98-007 | 12th January 1998
Luca Trevisan

Recycling Queries in PCPs and in Linearity Tests

We study query-efficient Probabilistically Checkable
Proofs (PCPs) and linearity tests. We focus on the number
of amortized query bits. A testing algorithm uses $q$ amortized
query bits if, for some constant $k$, it reads $qk$ bits and has
error probability at most $2^{-k}$. The best known ... 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 >>>

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

TR18-037 | 21st February 2018
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Inapproximability of Matrix $p \rightarrow q$ Norms

We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p} \] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been ... 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 >>>

TR19-148 | 1st November 2019
Amey Bhangale, Subhash Khot

Simultaneous Max-Cut is harder to approximate than Max-Cut

Revisions: 1

A systematic study of simultaneous optimization of constraint satisfaction problems was initiated in [BKS15]. The simplest such problem is the simultaneous Max-Cut. [BKKST18] gave a $.878$-minimum approximation algorithm for simultaneous Max-Cut which is {\em almost optimal} assuming the Unique Games Conjecture (UGC). For a single instance Max-Cut, [GW95] gave an ... 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 >>>

TR20-130 | 30th August 2020
Amey Bhangale, Subhash Khot

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant ... more >>>

ISSN 1433-8092 | Imprint