Events
Fall 2016
Uncertainty Seminar
Thursday, October 13th, 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.