Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

Local search proved to be an extremely useful tool when facing hard optimization problems (e.g., via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has it...