Fall 2016

Uncertainty Seminar

Oct 13, 2016 11:00 am – 12:30 pm 

Add to Calendar


Calvin Lab Rm 116

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

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.