Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HARDNESS OF APPROXIMATION:
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 >>>

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

TR21-177 | 22nd November 2021

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

TR22-061 | 30th April 2022
Amey Bhangale, Subhash Khot, Dor Minzer

#### On Approximability of Satisfiable $k$-CSPs: I

We consider the $P$-CSP problem for $3$-ary predicates $P$ on satisfiable instances. We show that under certain conditions on $P$ and a $(1,s)$ integrality gap instance of the $P$-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $s+\varepsilon$, for every constant $\varepsilon>0$. ... more >>>

ISSN 1433-8092 | Imprint