### DIMACS Theoretical Computer Science Seminar

Title: Reductions Between Expansion Problems

Speaker: **Madhur Tulsiani**, Princeton University

Date: Wednesday, February 16, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

I will talk about the problem of approximating the expansion of small
sets (of size $\delta n$) in a graph, conjectured to be hard by
Raghavendra and Steurer.

I will discuss an optimal self-reduction of the problem, which
starting from a weak qualitative version of the above conjecture,
gives an optimally strong version. This reduction also allows one to
reduce from approximating expansion for small sets to approximating
reduction at any desired "scale" in the graph, thus giving hardness
results for Balanced Separator, Minimum Linear Arrangement and other
expansion problems (assuming the hardness of the small-set expansion
problem).

The reduction uses long-codes like reductions from Unique Games.
However, the key technical difference here is a new folding operation
which identifies vertices of different long-code gadgets. This
destroys the local gadget-based structure of the resulting graph and
one cannot produce (say) a sparse balanced cut in the resulting graph
by using a balanced cut in the original graph (which was an
obstruction to proving hardness of expansion problems starting from
Unique Games).

Joint work with Prasad Raghavendra and David Steurer.