Unique Games and Expansion
Explore the Unique Games Conjecture (UGC) and its implications in computational complexity and algorithms in this 45-minute lecture by Mitali Bafna from Carnegie Mellon University. Delve into the concept of Unique Games, a 2-variable constraint satisfaction problem, and its role in hardness-of-approximation results for combinatorial optimization. Examine new algorithms for solving Unique Games instances on certifiable small-set expanders and graphs with certifiable global hypercontractivity. Gain insights into the breakthrough 2-2 Games hardness result and potential characteristics of hard Unique Games instances. Discover how low-degree sum-of-squares proofs can certify bounds on small-set-expansion and characterize non-expanding small sets in constraint graphs.