The Unique Games Conjecture and Graph Expansion

Опубликовано 17 августа 2016, 20:37

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 survey some recent results about the Unique Games Conjecture. The focus will be on an emerging 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. This result provides the first non-trivial sufficient condition for the truth of the conjecture. (Previously, only necessary conditions were known.) Based on joint work with Prasad Raghavendra.