Bhangale, Amey ;
Khot, Subhash
UGHardness to NPHardness by Losing Half
Abstract
The 2to2 Games Theorem of [Subhash Khot et al., 2017; Dinur et al., 2018; Dinur et al., 2018; Dinur et al., 2018] implies that it is NPhard to distinguish between Unique Games instances with assignment satisfying at least (1/2epsilon) fraction of the constraints vs. no assignment satisfying more than epsilon fraction of the constraints, for every constant epsilon>0. We show that the reduction can be transformed in a nontrivial way to give a stronger guarantee in the completeness case: For at least (1/2epsilon) 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 UGhardness results to NPhardness. We show:
1) Tight inapproximability of approximating independent sets in degree d graphs within a factor of Omega(d/(log^2 d)), where d is a constant.
2) NPhardness of approximate the Maximum Acyclic Subgraph problem within a factor of 2/3+epsilon, improving the previous ratio of 14/15+epsilon by Austrin et al. [Austrin et al., 2015].
3) For any predicate P^{1}(1) subseteq [q]^k supporting a balanced pairwise independent distribution, given a PCSP instance with value at least 1/2epsilon, it is NPhard to satisfy more than (P^{1}(1)/(q^k))+epsilon fraction of constraints.
BibTeX  Entry
@InProceedings{bhangale_et_al:LIPIcs:2019:10825,
author = {Amey Bhangale and Subhash Khot},
title = {{UGHardness to NPHardness by Losing Half}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {3:13:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10825},
URN = {urn:nbn:de:0030drops108258},
doi = {10.4230/LIPIcs.CCC.2019.3},
annote = {Keywords: NPhardness, Inapproximability, Unique Games Conjecture}
}
2019
Keywords: 

NPhardness, Inapproximability, Unique Games Conjecture 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 