### Revision(s):

__
Revision #1 to TR16-124 | 12th August 2016 12:09
__
#### On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

**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

**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

**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)$.