ECCC-Report TR16-124https://eccc.weizmann.ac.il/report/2016/124Comments and Revisions published for TR16-124en-usFri, 12 Aug 2016 12:09:33 +0300
Revision 1
| On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs |
Subhash Khot,
Dor Minzer,
Muli Safra
https://eccc.weizmann.ac.il/report/2016/124#revision1We 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)$.Fri, 12 Aug 2016 12:09:33 +0300https://eccc.weizmann.ac.il/report/2016/124#revision1
Comment 1
| On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs |
Subhash Khot,
Dor Minzer,
Muli Safra
https://eccc.weizmann.ac.il/report/2016/124#comment1We 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)$.Fri, 12 Aug 2016 12:08:37 +0300https://eccc.weizmann.ac.il/report/2016/124#comment1
Paper TR16-124
| On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs |
Subhash Khot
https://eccc.weizmann.ac.il/report/2016/124We 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)$.Fri, 12 Aug 2016 11:53:54 +0300https://eccc.weizmann.ac.il/report/2016/124