Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries
Howard AizensteinLisa HellersteinLeonard PittPublished in: FOCS (1992)
Keyphrases
- membership queries
- membership and equivalence queries
- exact learning
- efficient learning
- boolean functions
- learning algorithm
- uniform distribution
- dnf formulas
- learning theory
- equivalence queries
- pac learning
- monotone dnf
- computational learning theory
- target concept
- decision trees
- concept class
- inference rules
- model selection
- active learning