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 contains induced subgraphs that are themselves isomorphic to Grassmann graphs of lower orders. A set is called pseudorandom if its density is o(1) inside all subgraphs whose order is O(1) lower than that of .
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 -dimensional subspaces of an -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.