Reductions Between Expansion Problems

The small-set expansion conjecture introduced by Raghavendra and Steuerer is a natural hardness assumption concerning the problem of approximating edge expansion of small sets (of size $\delta n$) in graphs. It was shown to be intimately connected to the well-known Unique Games Conjecture.

Pursuing this line of research further, we obtain the following results:

-- We obtain a certain self-reducibility for the problem of approximating graph expansion. Via this reduction, starting from a qualitative hardness assumption about expansion of small sets, one can get a near-optimal quantitative result.

-- We show that the small-set expansion conjecture implies hardness for Balanced Separator and Minimum Linear Arrangement problems.

-- Starting from small-set expansion conjecture, we obtain hardness for Max-Cut and Unique Games on instances where the edge expansion closely matches the edge expansion of Gaussian space. As a consequence, this shows that the small-set expansion conjecture is indeed equivalent to a variant of Unique Games conjecture with expansion of small sets.

Compared to the usual reductions from Unique Games, the key technical difference in these reductions is a new folding operation which identifies vertices of different long-code gadgets. This allows us to derive consequences for say the balanced cuts in the graph obtained by the reduction, without having any assumptions on the balanced cuts in the starting graph.

Joint work with Prasad Raghavendra and David Steurer