A Glimpse of the Unique Games Conjecture
|Affiliation:||University of Waterloo|
|Room:||Mathematics 3 (M3) 2134|
The Unique Games Conjecture (UGC) asserts that one type of constraint satisfaction problem (related to a gap version of the max-cut problem) is NP-hard. This is an informal talk on the UGC. It will address some of the following: Where is it coming from? What is it? What has it done?
200 University Avenue West
Waterloo, ON N2L 3G1