Theory of Computing ------------------- Title : UG-hardness to NP-hardness by Losing Half Authors : Amey Bhangale and Subhash Khot Volume : 18 Number : 5 Pages : 1-28 URL : https://theoryofcomputing.org/articles/v018a005 Abstract -------- 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 $\epsilon> 0$, it is NP-hard to distinguish between Unique Games instances with some assignment satisfying at least a $(1/2)-\epsilon$ fraction of the constraints vs. no assignment satisfying more than an $\epsilon$ 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 $(1/2)-\epsilon$ 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(d/\log^2 d)$, for all sufficiently large constants $d$. 2. For all constants $\epsilon> 0$, NP-hardness of approximating the size of the Maximum Acyclic Subgraph within a factor of $(2/3)+\epsilon$, improving the previous ratio of $(14/15)+\epsilon$ by (Austrin et al., Theory of Computing, 2015). 3. For all constants $\epsilon> 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 $(1/2)-\epsilon$, it is NP-hard to satisfy more than a $\frac{|P^{-1}(1)|}{q^k}+\epsilon$ fraction of constraints. ---------------- A preliminary version of this paper appeared in the Proceedings of the 34th Computational Complexity Conference (CCC'19).