Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-124 | 12th August 2016 12:09

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

RSS-Feed




Revision #1
Authors: Subhash Khot, Dor Minzer, Muli Safra
Accepted on: 12th August 2016 12:09
Downloads: 1705
Keywords: 


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 $\left( 1- \frac{1}{\sqrt{2}} \right) 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)$.


Paper:

TR16-124 | 12th August 2016 11:50

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





TR16-124
Authors: Subhash Khot
Publication: 12th August 2016 11:53
Downloads: 3309
Keywords: 


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 $\left( 1- \frac{1}{\sqrt{2}} \right) 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)$.


Comment(s):

Comment #1 to TR16-124 | 12th August 2016 12:08

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

Authors: Subhash Khot, Dor Minzer, Muli Safra
Accepted on: 12th August 2016 12:08
Keywords: 


Comment:

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 $\left( 1- \frac{1}{\sqrt{2}} \right) 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)$.




ISSN 1433-8092 | Imprint