UG-hardness to NP-hardness by Losing Half

Amey Bhangale, Subhash Khot

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
JournalTheory of Computing
Volume18
DOIs
StatePublished - 2022

Keywords

  • NP-hardness
  • Unique Games Conjecture
  • inapproximability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'UG-hardness to NP-hardness by Losing Half'. Together they form a unique fingerprint.

Cite this