Theory of Computing
-------------------
Title     : On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs
Authors   : Subhash Khot, Dor Minzer, and Muli Safra
Volume    : 21
Number    : 10
Pages     : 1-55
URL       : https://theoryofcomputing.org/articles/v021a010

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 $(1- 1/\sqrt{2})n - o(n)$ or 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)$.

This article initiates and serves as the first installment in a line
of work by various subsets of the authors together with Dinur and
Kindler (with additional contributions by Barak, Kothari, and Steurer
(ITCS'19)) which led to a proof of the $2$-to-$2$ Games Conjecture
(albeit with imperfect completeness), which in particular implies the
NP-hardness results for independent set and vertex cover mentioned above.

---------------

A preliminary version of this paper appeared in the Proceedings of the
49th ACM Symposium on Theory of Computing</a> (STOC'17).