Oracles and Queries that are Sufficient for Exact Learning (Extended Abstract).

Nader H. Bshouty Richard Cleve Sampath Kannan Christino Tamon

Published in: COLT (1994)

Keyphrases

extended abstract
exact learning
membership queries
tree patterns
concept class
query complexity
number of queries needed
equivalence queries
membership and equivalence queries
learning theory
uniform distribution
dnf formulas
upper bound
lower bound
learning algorithm
boolean functions
database systems