The Sharp Power Law of Local Search on Expanders

Local search is a powerful heuristic in optimization and computer science, the complexity of which has been 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 → R. The local search problem is to find a vertex v that is a local minimum, i.e. with f (v) ≤ f (u) for all (u, v) ∈ E, using as few queries to the oracle 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 Ω √ n log n , where n is the number of vertices of the graph. This matches within a logarithmic factor the upper bound of O( √ n) for constant degree graphs from [Ald83], implying that steepest descent with a warm start is essentially an optimal algorithm for expanders. The best lower bound known from prior literature was Ω 8 √ n log n , shown by [SS04] 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 Ω n 1.5 g , where g is the vertex congestion of the graph; and Ω 4 s ∆ , where s is the separation number and ∆ is the maximum degree. For separation number the previous bound was Ω 8 s ∆ / log n , given by [SS04] for quantum and randomized algorithms. We also show a variant of the relational adversary method from [Aar06]. Our variant is asymptotically at least as strong as the version in [Aar06] for all randomized algorithms, as well as strictly stronger on some problems and easier to apply in our setting.