Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR16-124 | 12th August 2016 12:09

#### On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

Revision #1
Authors: Subhash Khot, Dor Minzer, Muli Safra
Accepted on: 12th August 2016 12:09
Keywords:

Abstract:

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about
Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in
a certain non-standard sense. A reduction that is sound in this non-standard sense
implies that it is NP-hard to distinguish whether an $n$-vertex graph has an independent
set of size $\left( 1- \frac{1}{\sqrt{2}} \right) n - o(n)$ or whether every independent
set has size $o(n)$, and consequently, that it is NP-hard to approximate the Vertex Cover problem within a
factor $\sqrt{2}-o(1)$.

### Paper:

TR16-124 | 12th August 2016 11:50

#### On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

TR16-124
Authors: Subhash Khot
Publication: 12th August 2016 11:53
Keywords:

Abstract:

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about
Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in
a certain non-standard sense. A reduction that is sound in this non-standard sense
implies that it is NP-hard to distinguish whether an $n$-vertex graph has an independent
set of size $\left( 1- \frac{1}{\sqrt{2}} \right) n - o(n)$ or whether every independent
set has size $o(n)$, and consequently, that it is NP-hard to approximate the Vertex Cover problem within a
factor $\sqrt{2}-o(1)$.

### Comment(s):

Comment #1 to TR16-124 | 12th August 2016 12:08

#### On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

Authors: Subhash Khot, Dor Minzer, Muli Safra
Accepted on: 12th August 2016 12:08
Keywords:

Comment:

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about
Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in
a certain non-standard sense. A reduction that is sound in this non-standard sense
implies that it is NP-hard to distinguish whether an $n$-vertex graph has an independent
set of size $\left( 1- \frac{1}{\sqrt{2}} \right) n - o(n)$ or whether every independent
set has size $o(n)$, and consequently, that it is NP-hard to approximate the Vertex Cover problem within a
factor $\sqrt{2}-o(1)$.

ISSN 1433-8092 | Imprint