Revision #1 Authors: Amey Bhangale, Subhash Khot

Accepted on: 5th June 2020 20:39

Downloads: 241

Keywords:

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 $(\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.

Minor revision in terms of better presentation and a small fix in the proof overview section.

TR19-004 Authors: Amey Bhangale, Subhash Khot

Publication: 13th January 2019 09:45

Downloads: 898

Keywords:

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 $(\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.