BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Tutorial - 2-2 Games Conjecture Kindler, Guy


The 2-to-1 games conjecture is the weaker sibling of the famous and important Unique-games conjecture of [Khot02]. A recent sequence of four papers resolved a version of that former conjecture, which might count as a step towards a proof of the Unique-games conjecture, and in any case invalidates some approaches for refuting it. The proof relies crucially on some Expansion properties of the Grassmann-graph, an object that to our knowledge was not studied before in the context of theoretical Computer Science. In this talk I will explain the 2-to-1 and the Unique-games conjectures and their implications, the Grassman graph and its relevance, and hopefully also some key ideas of the proofs. This is joint work with Irit Dinur, Subhash Khot, Dror Minzer, and Muli Safra

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International