TY - GEN
T1 - Towards a proof of the 2-to-1 games conjecture?
AU - Dinur, Irit
AU - Khot, Subhash
AU - Kindler, Guy
AU - Minzer, Dor
AU - Safra, Muli
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/6/20
Y1 - 2018/6/20
N2 - We present a polynomial time reduction from gap-3LIN to label cover with 2-to-1 constraints. In the “yes” case the fraction of satisfied constraints is at least 1 −, and in the “no” case we show that this fraction is at most, assuming a certain (new) combinatorial hypothesis on the Grassmann graph. In other words, we describe a combinatorial hypothesis that implies the 2-to-1 conjecture with imperfect completeness. The companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] makes some progress towards proving this hypothesis. Our work builds on earlier work by a subset of the authors [Khot, Minzer and Safra, STOC 2017] where a slightly different hypothesis was used to obtain hardness of approximating vertex cover to within factor of 2 − . The most important implication of this work is (assuming the hypothesis) an NP-hardness gap of 1/2 − vs. for unique games. In addition, we derive optimal NP-hardness for approximating the max-cut-gain problem, NP-hardness of coloring an almost 4-colorable graph with any constant number of colors, and the same 2 − NP-hardness for approximate vertex cover that was already obtained based on a slightly different hypothesis. Recent progress towards proving our hypothesis [Barak, Kothari and Steurer, ECCC TR18-077], [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] directly implies some new unconditional NPhardness results. These include new points of NP-hardness for unique games and for 2-to-1 and 2-to-2 games. More recently, the full version of our hypothesis was proven [Khot, Minzer and Safra, ECCC TR18-006].
AB - We present a polynomial time reduction from gap-3LIN to label cover with 2-to-1 constraints. In the “yes” case the fraction of satisfied constraints is at least 1 −, and in the “no” case we show that this fraction is at most, assuming a certain (new) combinatorial hypothesis on the Grassmann graph. In other words, we describe a combinatorial hypothesis that implies the 2-to-1 conjecture with imperfect completeness. The companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] makes some progress towards proving this hypothesis. Our work builds on earlier work by a subset of the authors [Khot, Minzer and Safra, STOC 2017] where a slightly different hypothesis was used to obtain hardness of approximating vertex cover to within factor of 2 − . The most important implication of this work is (assuming the hypothesis) an NP-hardness gap of 1/2 − vs. for unique games. In addition, we derive optimal NP-hardness for approximating the max-cut-gain problem, NP-hardness of coloring an almost 4-colorable graph with any constant number of colors, and the same 2 − NP-hardness for approximate vertex cover that was already obtained based on a slightly different hypothesis. Recent progress towards proving our hypothesis [Barak, Kothari and Steurer, ECCC TR18-077], [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] directly implies some new unconditional NPhardness results. These include new points of NP-hardness for unique games and for 2-to-1 and 2-to-2 games. More recently, the full version of our hypothesis was proven [Khot, Minzer and Safra, ECCC TR18-006].
KW - 2-to-2 games
KW - Grassmann graph
KW - PCP
KW - Unique games
UR - http://www.scopus.com/inward/record.url?scp=85049907296&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049907296&partnerID=8YFLogxK
U2 - 10.1145/3188745.3188804
DO - 10.1145/3188745.3188804
M3 - Conference contribution
AN - SCOPUS:85049907296
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1297
EP - 1306
BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Henzinger, Monika
A2 - Kempe, David
A2 - Diakonikolas, Ilias
PB - Association for Computing Machinery
T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018
Y2 - 25 June 2018 through 29 June 2018
ER -