***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Muli Safra (U. Tel Aviv)

Thursday 13th September, 3:00 in Fine Hall 224.

Title: The 2-to-2 Games Conjecture via expansion on the Grassmann graph

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.


		----------------------------------

Next week: Ehud Friedgut

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)