The Unique Games Conjecture, proposed by Subhash Khot [Khot 2002], is a complexity theoretic assumption that if true yields optimal inapproximability results of several optimization problems. Since it was proposed in 2002, the theoretical computer science community has spent equal effort in proving and refuting the conjecture and till recently were evenly divided in their belief in the conjecture. Recently, in a remarkable sequence of 4 papers, 5 researchers (Minzer, Khot, Safra, Dinur and Kindler) proved a weaker version of the conjecture, called the 2-to-2 Games conjecture (or now, the 2-to-2 Games Theorem).
At the heart of their proof is a study of the Grassman Graph and its expansion properties. The Grassman Graph is a graph whose vertices are k-dimensional subspaces of GF(2)^m and two subspaces are connected if they intersect on a (k-1)-dimensional subspace. This graph is known to have several small structured sets that do not expand. A crucial element of the proof goes towards showing that any set that does not have such an algebraic structure does in fact expand. In this survey talk, I'll explain the UGC conjecture, its implications, the 2-to-2 Games Theorem, the Grassman Graph, its expansion properties and some keys steps in the proof.
No background (but for a familiarity with complexity theory) will be assumed.
Talk based on the following papers:
1. Subhash Khot, Dor Minzer, and Muli Safra." On independent sets,
2-to-2 games, and Grassmann graphs", 2017.
2. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.
"Towards a proof of the 2-to-1 games conjecture?", 2018
3. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.
"On non-optimally expanding sets in grassmann graphs", 2018.
4. Subhash Khot, Dor Minzer, and Muli Safra. "Pseudorandom sets in
grassmann graph have near-perfect expansion", 2018.