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.