Tsuyoshi Morioka

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

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

Tim Roughgarden

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 >>>Pavel Hubacek, Eylon Yogev

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

Ilario Bonacina, Neil Thapen

Recently it was shown that PLS is not contained in PPADS (ECCC report TR22-058). We show that this separation already implies that PLS is not contained in PPP. These separations are shown for the decision tree model of TFNP and imply similar separations in the type-2, relativized model.

Important note. ... more >>>

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

A problem is downward self-reducible if it can be solved efficiently given an oracle that returns

solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is

well studied and it is known that all downward self-reducible problems are in PSPACE. In this

paper, we initiate the study of ...
more >>>