ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-063 | 22nd February 2017 13:07

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

RSS-Feed




Revision #1
Authors: Pavel Hubacek, Eylon Yogev
Accepted on: 22nd February 2017 13:07
Downloads: 22
Keywords: 


Abstract:

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 problem is defined by a continuous function, which might offer an advantage when performing the local search. This leads us to study the following natural question: How hard is continuous local search? The computational complexity of such search problems is captured by the complexity class $\mathbf{CLS}$ which is contained in the intersection of $\mathbf{PLS}$ and $\mathbf{PPAD}$, two important subclasses of $\mathbf{TFNP}$ (the class of $\mathbf{NP}$ search problems with a guaranteed solution).

In this work, we show the first hardness results for $\mathbf{CLS}$ (the smallest non-trivial class among the currently defined subclasses of $\mathbf{TFNP}$). Our hardness results are in terms of black-box (where only oracle access to the function is given) and white-box (where the function is represented succinctly by a circuit). In the black-box case, we show instances for which any (computationally unbounded) randomized algorithm must perform exponentially many queries in order to find a local optimum. In the white-box case, we show hardness for computationally bounded algorithms under cryptographic assumptions.

As our main technical contribution we introduce a new total search problem which we call End-Of-Metered-Line. The special structure of End-Of-Metered-Line enables us to: (1) show that it is contained in $\mathbf{CLS}$, (2) prove hardness for it both in the black-box and the white-box setting, and (3) extend to $\mathbf{CLS}$ a variety of results previously known only for $\mathbf{PPAD}$.



Changes to previous version:

Added corollaries of recent works.


Paper:

TR16-063 | 18th April 2016 16:06

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





TR16-063
Authors: Pavel Hubacek, Eylon Yogev
Publication: 18th April 2016 22:09
Downloads: 435
Keywords: 


Abstract:

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 problem is defined by a continuous function, which might offer an advantage when performing the local search. This leads us to study the following natural question: How hard is continuous local search? The computational complexity of such search problems is captured by the complexity class $\mathbf{CLS}$ which is contained in the intersection of $\mathbf{PLS}$ and $\mathbf{PPAD}$, two important subclasses of $\mathbf{TFNP}$ (the class of $\mathbf{NP}$ search problems with a guaranteed solution).

In this work, we show the first hardness results for $\mathbf{CLS}$ (the smallest non-trivial class among the currently defined subclasses of $\mathbf{TFNP}$). Our hardness results are in terms of black-box (where only oracle access to the function is given) and white-box (where the function is represented succinctly by a circuit). In the black-box case, we show instances for which any (computationally unbounded) randomized algorithm must perform exponentially many queries in order to find a local optimum. In the white-box case, we show hardness for computationally bounded algorithms under cryptographic assumptions.

As our main technical contribution we introduce a new total search problem which we call End-Of-Metered-Line. The special structure of this problem enables us to: (1) show that End-Of-Metered-Line is contained in $\mathbf{CLS}$, and (2) prove hardness for it both in the black-box and the white-box setting.



ISSN 1433-8092 | Imprint