Scott Aaronson

The problem of finding a local minimum of a black-box function is central

for understanding local search as well as quantum adiabatic algorithms.

For functions on the Boolean hypercube {0,1}^n, we show a lower bound of

Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to

solve this ...
more >>>

Matthew Hastings

Given a MAX-2-SAT instance, we define a local maximum to be an assignment such that changing any single variable reduces the number of satisfied clauses. We consider the question of the number of local maxima hat an instance of MAX-2-SAT can have. We give upper bounds in both the sparse ... more >>>