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