Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with local optima:
TR03-057 | 21st July 2003
Scott Aaronson

Lower Bounds for Local Search by Quantum Arguments

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 >>>

TR16-163 | 25th October 2016
Matthew Hastings

Local Maxima and Improved Exact Algorithm for MAX-2-SAT

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 >>>

ISSN 1433-8092 | Imprint