- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Tutorial - 2-2 Games Conjecture
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Tutorial - 2-2 Games Conjecture Kindler, Guy
Description
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 Metadata
| Title |
Tutorial - 2-2 Games Conjecture
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2018-08-13T09:07
|
| Description |
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
|
| Extent |
87.0
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Hebrew University of Jerusalem
|
| Series | |
| Date Available |
2019-03-27
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0377619
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International