Volume 18 (2022) Article 5 pp. 1-28
CCC 2019 Special Issue

UG-hardness to NP-hardness by Losing Half

by Amey Bhangale and Subhash Khot

Received: July 24, 2019
Revised: March 4, 2022
Published: March 15, 2022

The $2$-to-$2$ Games Theorem (Khot et al., STOC'17, Dinur et al., STOC'18 [2 papers], Khot et al., FOCS'18) shows that for all constants $\varepsilon> 0$, it is NP-hard to distinguish between Unique Games instances with some assignment satisfying at least a $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than an $\varepsilon$ fraction of the constraints. We show that the reduction can be transformed in a non-trivial way to give stronger completeness: For at least a $(\frac{1}{2}-\varepsilon)$ fraction of the vertices on one side, all the constraints associated with them in the Unique Games instance can be satisfied.

We use this guarantee to convert known UG-hardness results to NP-hardness. We show:

1. Tight inapproximability of the maximum size of independent sets in degree-$d$ graphs within a factor of $\Omega\left(\frac{d}{\log^2 d}\right)$, for all sufficiently large constants $d$.
2. For all constants $\varepsilon> 0$, NP-hardness of approximating the size of the Maximum Acyclic Subgraph within a factor of $\frac{2}{3}+\varepsilon$, improving the previous ratio of $\frac{14}{15}+\varepsilon$ by (Austrin et al., Theory of Computing, 2015).
3. For all constants $\varepsilon> 0$ and for any predicate $P^{-1}(1) \subseteq [q]^k$ supporting a balanced pairwise independent distribution, given a $P$-CSP instance with value at least $\frac{1}{2}-\varepsilon$, it is NP-hard to satisfy more than a $\frac{|P^{-1}(1)|}{q^k}+\varepsilon$ fraction of constraints.

----------------

A preliminary version of this paper appeared in the Proceedings of the 34th Computational Complexity Conference (CCC'19).

DOI: 10.4086/toc.2022.v018a005

© 2022 Amey Bhangale and Subhash Khot
Licensed under a Creative Commons Attribution License (CC-BY)