ECCC-Report TR19-004https://eccc.weizmann.ac.il/report/2019/004Comments and Revisions published for TR19-004en-usFri, 05 Jun 2020 20:39:03 +0300
Revision 1
| UG-hardness to NP-hardness by Losing Half |
Amey Bhangale,
Subhash Khot
https://eccc.weizmann.ac.il/report/2019/004#revision1The $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 $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>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 $(\frac{1}{2}-\varepsilon)$ 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 $\Omega\left(\frac{d}{\log^2 d}\right)$, where $d$ is a constant.
2. NP-hardness of approximate Maximum Acyclic Subgraph problem within a factor of $\frac{2}{3}+\varepsilon$, improving the previous ratio of $\frac{14}{15}+\varepsilon$ by Austrin et al.[AMW15].
3. For any predicate $P^{-1}(1) \subseteq [q]^k$ supporting balanced pairwise independent distribution, given a $P$-CSP instance with value at least $\frac{1}{2}-\varepsilon$, it is NP-hard to satisfy more than $\frac{|P^{-1}(1)|}{q^k}+\varepsilon$ fraction of constraints.
Fri, 05 Jun 2020 20:39:03 +0300https://eccc.weizmann.ac.il/report/2019/004#revision1
Paper TR19-004
| UG-hardness to NP-hardness by Losing Half |
Amey Bhangale,
Subhash Khot
https://eccc.weizmann.ac.il/report/2019/004The $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 $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>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 $(\frac{1}{2}-\varepsilon)$ 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 $\Omega\left(\frac{d}{\log^2 d}\right)$, where $d$ is a constant.
2. NP-hardness of approximate Maximum Acyclic Subgraph problem within a factor of $\frac{2}{3}+\varepsilon$, improving the previous ratio of $\frac{14}{15}+\varepsilon$ by Austrin et al.[AMW15].
3. For any predicate $P^{-1}(1) \subseteq [q]^k$ supporting balanced pairwise independent distribution, given a $P$-CSP instance with value at least $\frac{1}{2}-\varepsilon$, it is NP-hard to satisfy more than $\frac{|P^{-1}(1)|}{q^k}+\varepsilon$ fraction of constraints.
Sun, 13 Jan 2019 09:45:37 +0200https://eccc.weizmann.ac.il/report/2019/004