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

Pavel Hubácek Eylon Yogev

Published in: Electron. Colloquium Comput. Complex. (2016)

Keyphrases

query complexity
lower bound
concept class
learning theory
vc dimension
np hard
upper bound
concept classes

worst case
data complexity
membership queries
optimal solution
dnf formulas
equivalence queries
np complete

concept learning
upper and lower bounds
genetic algorithm
sample complexity
exact learning
computational complexity
search algorithm

simulated annealing
efficient learning
phase transition
inductive inference
pac learning
lower and upper bounds
uniform distribution