Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pavel Hubacek:

TR16-199 | 15th December 2016
Pavel Hubacek, Moni Naor, Eylon Yogev

The Journey from NP to TFNP Hardness

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one ... 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