## Worst-Case to Expander-Case Reductions

by Amir Abboud and Nathan Wallheimer

#### Oded's comments

I believe the abstract speaks for itself, but let me add my own perspective.
It seems that the simple gadget reductions that are used in some
(*but not all*) of the cases, demonstrate that for these cases
(or problems) the restriction to expanders is a red herring.
Yet, in other cases, new reductions are shown using the
expander decomposition method, and a natural question that arises
is whether in these cases a ``simple gadget reduction'' fails.
Needless to say, this requires defining the aforementioned notion
and possibly relying on computational conjectures.

#### The original abstract

In recent years, the expander decomposition method was used to develop
many graph algorithms, resulting in major improvements to
longstanding complexity barriers.
This powerful hammer has led the community to
(1) believe that most problems are as easy on worst-case graphs
as they are on expanders,
and (2) suspect that expander decompositions are the key to breaking
the remaining longstanding barriers in fine-grained complexity.
We set out to investigate the extent to which these two things are true
(and for which problems). Towards this end, we put forth the concept
of worst-case to expander-case self-reductions.
We design a collection of such reductions for fundamental graph problems,
verifying belief (1) for them. The list includes k-Clique, 4-Cycle,
Maximum Cardinality Matching, Vertex-Cover, and Minimum Dominating Set.
Interestingly, for most (but not all) of these problems the proof is via
a simple gadget reduction, not via expander decompositions,
showing that this hammer is effectively useless
against the problem and contradicting (2).

Available from
the
proceedings of 14th ITCS.

Back to
list of Oded's choices.