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

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. abc says:
2. 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.)

• Gil Kalai says:

Thanks Lior and James. James is the statement you mentioned a consequence of the unique game conjecture?

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

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/