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 ε > 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.
Original language | English (US) |
---|---|
Journal | Theory of Computing |
Volume | 18 |
DOIs | |
State | Published - 2022 |
Keywords
- NP-hardness
- Unique Games Conjecture
- inapproximability
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics