CS 298-2
Theory Seminar
Ryan O'Donnell
Microsoft Research
In the first part of this talk I will give my biased opinions about
Khot's now-notorious Unique Games Conjecture (UGC). I will try to argue
that hardness-of-approximation results based on the UGC are meaningful,
by relating them to the title question, "Are there any more polynomial
time algorithms?".
In the second part of the talk I will show how several UGC-hardness
results can be put in a unified framework based on semidefinite programs
(SDP) in Gaussian space. I'll illustrate the framework with a
"textbook" example, showing UGC-hardness of the following problem: Given
a graph whose maximum cut has (fractional) size 1/2 + eps, find a cut
with size 1/2 + eps/log(1/eps).