The Query Complexity of Local Search in Rounds on General Graphs

Simina Brânzei, Ioannis Panageas, Dimitris Paparas

We analyze the query complexity of finding a local minimum in $t$ rounds on general graphs. More precisely, given a graph $G=(V,E)$ and oracle access to an unknown function $f :…