Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture

Posted on January 10, 2018 by Gil Kalai

Update: A related blog post by Boaz Barak: Unique Games Conjecture – halfway there?

The 2-to-2 Games Conjecture is a somewhat weaker form of Khot’s unique game conjecture.

The paper is: Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion by Subhash Khot, Dor Minzer and Muli Safra. (See this post for a team photo and another breakthrough.)

Here is the abstract: We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes the proof of the 2-to-2 Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a contribution from [BKT].

The Grassmann graph Gr_{global} contains induced subgraphs Gr_{local} that are themselves isomorphic to Grassmann graphs of lower orders. A set is called pseudorandom if its density is o(1) inside all subgraphs Gr_{local} whose order is O(1) lower than that of Gr_{global}.

We prove that pseudorandom sets have expansion 1−o(1), greatly extending the results and techniques in [DKKMS-2].

This is a great result. The Grassman graphs are graphs with vertices corresponding to k-dimensional subspaces of an n-dimensional vector space over a (small as possible) field. Of course, they are of much interest to combinatorialists.

The earlier papers mentioned are:

[KMS] Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and Grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 576–589, 2017.

[DKKMS1]    Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra, Towards a Proof of the 2-to-1 Games Conjecture?

[DKKMS2] – Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra,  On Non-Optimally Expanding Sets in Grassmann Graphs.

[BKT] Boaz Barak, Pravesh Kothari, and David Steurer – personal communication.

A field with one element

Talking to the authors one gets the impression that what seems to be missing for proving the unique game conjecture is a field with one element.

This entry was posted in Combinatorics, Computer Science and Optimization, Updates and tagged , , . Bookmark the permalink.

11 Responses to Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture

  2. Lior Silberman says:
    January 11, 2018 at 3:42 am

    One of the main motivations in studying the UGC has been that various problems having shown to be UGC-hard. Does this new partial result suffice to to give unconditional hardness results for some interesting problems?

    Reply
    • James says:
      January 11, 2018 at 8:58 am

      Lior, yes: See Appendix B of their paper. For instance, the UGC implies that it is NP-hard to do better than a 2-approximation for Vertex Cover. Their result shows it is NP-hard to do better than sqrt{2} (improving over the previous 1.36… bound of Dinur-Safra). This is a consequence of a hardness result for Independent Set that is somewhat more interesting.

      I believe the lack of perfect completeness prevents them from obtaining the following consequence (Dinur-Regev-Mossel?): For every A > B > 2, it is NP-hard to A-color a B-colorable graph. (This is still open.)

      Reply
  3. James says:
    January 17, 2018 at 10:07 am

    Hi Gil, such statements cannot be based on the UGC in any standard way because perfectly satisfiable UG instances are easy to solve. Since the “yes” instances for UG are 1-eps satisfiable, it seems tricky for a reduction to produce a genuinely k-colorable graph (as opposed to a graph that can be k-colored with an f(eps)-fraction of violated edges). This was one of the potential benefits of a 2-to-1 conjecture; this problem is still potentially hard even when the yes instances are 100% satisfiable.

    The paper I was referring to (Dinur-Mossel-Regev) is here: https://arxiv.org/pdf/cs/0504062.pdf

    The 2-to-1 conjecture would show that it is NP-hard to k-color a 4-colorable graph for any constant k. I think the Khot-Minzer-Safra paper gives an “almost” version where the yes instances are 4-colorable with an eps-fraction of violated edges.

    Reply

  4. Pingback: Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachaterian theorem, and More. | Combinatorics and more

  5. Gil Kalai says:
    April 24, 2018 at 5:31 pm

    Two additional relevant papers: Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture by Boaz Barak, Pravesh Kothari, David Steurer https://eccc.weizmann.ac.il/report/2018/077/

    and

    Small Set Expansion in The Johnson Graph | Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra https://eccc.weizmann.ac.il/report/2018/078/

    Reply
  6. Gil Kalai says:
    April 25, 2018 at 9:34 pm

    A beautiful article First Big Steps Toward Proving the Unique Games Conjecture by Erica Klarreich
    https://www.quantamagazine.org/computer-scientists-close-in-on-unique-games-conjecture-proof-20180424/

    Reply

  7. Pingback: Boolean Degree 1 Functions on Association Schemes | Ratio Bound – A Combinatorics Blog

  8. Timothy Chow says:
    April 21, 2019 at 2:36 am

    Gil, can you elaborate on your remark about the field with one element? How might a better understanding of the field with one element lead to a proof of the unique games conjecture?

    Reply

  9. Pingback: Greatest Hits 2015-2022, Part I | Combinatorics and more

Leave a comment