Wednesday, September 10, 2014 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
A Glimpse of the Unique Games Conjecture
| Speaker: | Joesph Cheryian |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics 3 (M3) 2134 |
Abstract:
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?