Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PLS:
TR03-051 | 20th June 2003
Tsuyoshi Morioka

The Relative Complexity of Local Search Heuristics and the Iteration Principle

Johnson, Papadimitriou and Yannakakis introduce the class $\PLS$
consisting of optimization problems for which efficient local-
search heuristics exist. We formulate a type-2 problem $\iter$
that characterizes $\PLS$ in style of Beame et al., and prove
a criterion for type-2 problems to be nonreducible to $\iter$.
As a corollary, ... more >>>

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

TR15-153 | 21st September 2015
Tim Roughgarden

Computing Equilibria: A Computational Complexity Perspective

Computational complexity is the subfield of computer science that rigorously studies the intrinsic difficulty of computational problems. This survey explains how complexity theory defines “hard problems”; applies these concepts to several equilibrium computation problems; and discusses implications for computation, games, and behavior. We assume minimal prior background in computer science.

... more >>>

TR16-063 | 18th April 2016
Pavel Hubacek, Eylon Yogev

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

Revisions: 1

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 its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts the optimization ... more >>>

ISSN 1433-8092 | Imprint