Events

Fall 2016

# Uncertainty Seminar

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

Parent Program:

Speaker:

Location:

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.