Almost tight bound on the query complexity of generalized Simon's problem.

Zekun Ye Yunqi Huang Yuyi Wang Lvzhou Li

Published in: CoRR (2019)

Keyphrases

query complexity
upper bound
lower bound
vc dimension
concept class
worst case
data complexity
membership queries
exact learning
concept classes
sample complexity
knowledge representation
resource allocation
expressive power
generalization error
upper and lower bounds
optimal solution