Computer Science/Discrete Mathematics Seminar I

The Unique Games Conjecture (Khot, 2002) is a central open question about hardness of approximation. In recent years, a sequence of works showed that the truth of this conjecture would have profound implications: If the conjecture is true, then current algorithmic techniques (semidefinite relaxations) are optimal for a large range of optimization problems, in the sense that no efficient algorithm can achieve a better approximation guarantee for any of these problems. In this talk, I will present a connection between the Unique Games Conjecture and the problem of approximating the expansion profile of graphs. In particular, we show that the Unique Games Conjecture is true if the expansion of small sets in graphs is hard to approximate in a certain regime. This result provides the first non-trivial sufficient condition for the truth of the conjecture. (Previously, only implications of the truth of the conjecture were known.) Joint work with Prasad Raghavendra.