  A recent paper by Abboud and Wallheimer [ITCS 2023] presents self-reductions
for various fundamental graph problems, which transform worst-case instances to
expanders, thus proving that the complexity remains unchanged if the input is
assumed to be an expander. An interesting corollary of their self-reductions is
that if some problem admits such reduction, then the popular algorithmic
paradigm based on expander-decompositions is useless against it. In this paper,
we improve their core gadget, which augments a graph to make it an expander
while retaining its important structure. Our new core construction has the
benefit of being simple to analyze and generalize while obtaining the following
results:
  1. A derandomization of the self-reductions, showing that the equivalence
between worst-case and expander-case holds even for deterministic algorithms,
and ruling out the use of expander-decompositions as a derandomization tool.
  2. An extension of the results to other models of computation, such as the
Fully Dynamic model and the Congested Clique model. In the former, we either
improve or provide an alternative approach to some recent hardness results for
dynamic expander graphs by Henzinger, Paz, and Sricharan [ESA 2022].
  In addition, we continue this line of research by designing new
self-reductions for more problems, such as Max-Cut and dynamic Densest
Subgraph, and demonstrating that the core gadget can be utilized to lift lower
bounds based on the OMv Conjecture to expanders.
