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

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.

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

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

  1. 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?

    • James says:

      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.)

  2. James says:

    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.

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

  4. Gil Kalai says:

    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/

  5. Gil Kalai says:

    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/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s