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.