Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with CLS:
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 >>>

TR22-133 | 20th September 2022
Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

Downward Self-Reducibility in TFNP

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

ISSN 1433-8092 | Imprint