The Unique Games Conjecture and Graph Expansion

Date

February 2, 2010

Overview

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.

Speakers

David Steurer

David Steurer is a Ph.D. student in the Computer Science Department of Princeton University. His adviser is Sanjeev Arora. David’s main research interests are approximation algorithms, combinatorial optimization problems, and mathematical programming relaxations.

People

‚Äč