## Worst-Case to Expander-Case Reductions: Derandomized and Generalized

by Amir Abboud and Nathan Wallheimer

#### Oded's comments

While previous paper presented such
a randomized resuction, the current work presents a deterministoic
reduction as well as other reductions that fit other contexts
(e.g., the dynamic graph contents).

For $n$-vertex graphs that are $d$-regular,
it suffices to connect the input graph to $n$ auxiliary vertices
by using a $d$-regular bipartite expander.
A natural generalization to non-regular graphs would require
a construction of bipartirte expanders for any desired degree sequences.
While proving such a construction may be of independent interest,
the authors take an alternative path. Specifically, they connect
the input graph to $n$ intermedaite vertices (by using a load
balancing scheme) and place a $2m/n$-regular bipartite expander
between these intermediate vertices and $n$ auxiliary vertices,
where $m$ denotes the number of edges in the original graph.
This is done by increasing the degree of each original vertex
by a factor of two and having $2m/n$ edges from each intermediate
vertex to the original vertices.

Expansion from the original vertices is guaranteed by the edges
to the intermediate vertices, and expansion from other vertices
is guaranteed by the bipartite expnader.

Back to
list of Oded's choices.