  Local search is a powerful heuristic in optimization and computer science,
the complexity of which was studied in the white box and black box models. In
the black box model, we are given a graph $G = (V,E)$ and oracle access to a
function $f : V \to \mathbb{R}$. The local search problem is to find a vertex
$v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in E$,
using as few queries as possible. The query complexity is well understood on
the grid and the hypercube, but much less is known beyond.
  We show the query complexity of local search on $d$-regular expanders with
constant degree is $\Omega\left(\frac{\sqrt{n}}{\log{n}}\right)$, where $n$ is
the number of vertices. This matches within a logarithmic factor the upper
bound of $O(\sqrt{n})$ for constant degree graphs from Aldous (1983), implying
that steepest descent with a warm start is an essentially optimal algorithm for
expanders. The best lower bound known from prior work was
$\Omega\left(\frac{\sqrt[8]{n}}{\log{n}}\right)$, shown by Santha and Szegedy
(2004) for quantum and randomized algorithms.
  We obtain this result by considering a broader framework of graph features
such as vertex congestion and separation number. We show that for each graph,
the randomized query complexity of local search is
$\Omega\left(\frac{n^{1.5}}{g}\right)$, where $g$ is the vertex congestion of
the graph; and $\Omega\left(\sqrt[4]{\frac{s}{\Delta}}\right)$, where $s$ is
the separation number and $\Delta$ is the maximum degree. For separation number
the previous bound was $\Omega\left(\sqrt[8]{\frac{s}{\Delta}}
/\log{n}\right)$, given by Santha and Szegedy for quantum and randomized
algorithms.
  We also show a variant of the relational adversary method from Aaronson
(2006), which is asymptotically at least as strong as the version in Aaronson
(2006) for all randomized algorithms and strictly stronger for some problems.
