## 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 (^{1}2 − ε) 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 (^{1}2 − ε) 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. log^{2} 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