The Unique-Games problem asks, given a system of linear equations over a finite field in which each equation contains 2 variables, to distinguish between the case that it is nearly satisfiable (i.e. all but 1% of the equations can be satisfied), and the case almost no equations can be
satisfied (i.e. at most 1%). The Unique-Games Conjecture, posed by Khot in 2002, postulates that this problem is NP-hard in the worst case. This conjecture has become a central open problem in theoretical computer science, mainly due to its far-reaching consequences in the field of hardness of approximation.

A recent line of study pursued a new attack on a closely related conjecture, called the 2-to-2 Games Conjecture. The approach is based on a mathematical object called the Grassmann graph, and relies on the study of edge-expansion in this graph. More specifically, the study of sets of vertices in the Grassmann graph that contain even a tiny fraction of the edges incident to the set.

We have recently concluded this line of research, thereby proving the 2-to-2 Games Conjecture. This talk discusses the 2-to-2 Games Conjecture, its implications and the line of study mentioned above.