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