Revised: March 4, 2022
Published: March 15, 2022
Abstract: [Plain Text Version]
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:
- 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$.
- 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).
- 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).
Licensed under a Creative Commons Attribution License (CC-BY)