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 ε > 0, it is NP-hard to distinguish between Unique Games instances with some assignment satisfying at least a (12 − ε) fraction of the constraints vs. no assignment satisfying more than an ε 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 (12 − ε) 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 Ω( d, for all sufficiently large constants d. log2 d.
- Unique Games Conjecture
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics