2023-07-19 |
13:00-13:45 |
2023-07-19,13:00-13:45 | LR13 (A7 3F) |
07-19 Afternoon TCIS Lecture Room 13 (A7 3F)
|
Speaker |
The 2-to-1 Games Theorem The Unique Games Conjecture is a central open problem in Theoretical Computer Science, which if true, would imply a wide plethora of tight hardness of approximation results. In this talk, I'll discuss the recent proof of a ``close sibling" of this conjecture, namely the 2-to-1 Games Theorem. The 2-to-1 Games result goes ``half of the way" towards a positive resolution of the Unique Games Conjecture.
|