Seminar Room, Room 261, Ziskind Building on Monday, March 14, 2011 14:30 - 15:30 Prasad Raghavendra Georgia Institute of Technology will speak on Approximating Graph Expansion: Connections, Algorithms and Reductions Abstract: Approximating edge expansion, equivalently finding sparse cuts in graphs is a fundamental problem in combinatorial optimization that has received considerable attention in both theory and practice. Yet, the complexity of approximating edge expansion in graphs is poorly understood. Particularly, worse is the understanding of the approximability of the expansion of small sets in graphs. More formally, current algorithmic or hardness results do not settle the approximability of the following problem: Given a regular graph $G$ and a very small constant $c$, find a set $S$ of $cn$ vertices in the graph such that minimum number of edges cross the set $S$. Recently it was shown that the complexity of this problem is closely tied to the Unique Games Conjecture. Furthermore, we show that the hardness of this problem is a natural assumption that generalizes the unique games conjecture, and yields hardness for problems like Balanced Separator and Minimum Linear arrangement.