When Won't Membership Queries Help?
Dana AngluinMichael KharitonovPublished 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