We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

From the Grassmann graph to 2-to-2 games

Formal Metadata

Title
From the Grassmann graph to 2-to-2 games
Alternative Title
Tutorial - 2-2 Games Conjecture
Title of Series
Number of Parts
17
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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.