A large lower bound on the query complexity of a simple boolean function.

Published in: Inf. Process. Lett. (2005)

Keyphrases

boolean functions
membership queries
lower bound
query complexity
concept class
uniform distribution
upper bound
dnf formulas
exact learning
equivalence queries
learning algorithm
np hard
statistical queries
dnf formulae
objective function
target concept