UG-hardness to NP-hardness by Losing Half

摘要

The 2 -to- 2 Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least ( 2 1 ? ) fraction of the constraints vs no assignment satisfying more than fraction of the constraints, for every constant 0" 0 . We show that the reduction can be transformed in a non-trivial way to give a stronger guarantee in the completeness case: For at least ( 2 1 ? ) 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 the known UG-hardness results to NP-hardness. We show:1. Tight inapproximability of approximating independent sets in a degree d graphs within a factor of d log 2 d , where d is a constant. 2. NP-hardness of approximate Maximum Acyclic Subgraph problem within a factor of 3 2 + , improving the previous ratio of 15 14 + by Austrin et al.[AMW15]. 3. For any predicate P ? 1 (1) [ q ] k supporting balanced pairwise independent distribution, given a P -CSP instance with value at least 2 1 ? , it is NP-hard to satisfy more than q k P ? 1 (1) + fraction of constraints.