When Won't Membership Queries Help?

Dana Angluin Michael Kharitonov

Published in: J. Comput. Syst. Sci. (1995)

Keyphrases

membership queries
exact learning
uniform distribution
learning algorithm
boolean functions

dnf formulas
pac learning
efficient learning
target concept
query complexity

monotone dnf
read once formulas
concept class
concept classes
equivalence queries

agnostic learning
remains np hard
membership and equivalence queries
monotone dnf formulas
dnf formulae