Uncertainty Seminar

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 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).
Joint work with Subhash Khot and Minzer Dor.