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