Title:  Graph Expansion and the Unique Games Conjecture

Speaker:  David Steurer, Princeton 

Abstract: 

We investigate the connection between Graph Expansion and the Unique
Games Conjecture.  The edge expansion of a subset of vertices S in a
graph G measures the fraction of edges that leave S.  Approximating
the expansion of small linear-sized sets is a natural optimization
question that is a variant of the well-studied Sparsest Cut problem.
However, no known algorithms can even distinguish between almost
perfect edge expansion, and almost no edge expansion.

Our main results are as follows:

1.) We show that a simple decision version of the problem of
approximating small-set expansion reduces to Unique Games.  Thus if
approximating edge expansion of small sets is hard, then the Unique
Games Conjecture is true.  Alternatively, a refutation of the Unique
Games Conjecture will yield better algorithms to approximate small-set
expansion in graphs.

This result is the first non-trivial ``reverse'' reduction from a
natural optimization problem to Unique Games.

2.) Under a slightly stronger version of the Unique Games Conjecture
that assumes mild expansion of small sets, we show that it is hard to
approximate small-set expansion.

3.) On instances with sufficiently good expansion of small sets, we
show that Unique Games is easy to solve by extending the techniques of
Arora et al (STOC'08).

Joint work with Prasad Raghavendra.