Query-Complexity Amplification for Random Oracles.

Grégory Demay Peter Gazi Ueli Maurer Björn Tackmann

Published in: ICITS (2015)

Keyphrases

query complexity
concept class
membership queries
data complexity
concept classes
learning theory
exact learning
vc dimension
dnf formulas
expressive power
pac learning
training data
lower bound
upper bound
concept learning