The Sharp Power Law of Local Search on Expanders

Simina Brânzei, Davin Choo, Nicholas Recker

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…