Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs

Hang Dinh, Alexander Russell

We study the problem of \emph{local search} on a graph. Given a real-valued black-box function f on the graph's vertices, this is the problem of determining a local minimum of f--a…