On the Limits of Proper Learnability of Subclasses of DNF Formulas.

Krishnan Pillaipakkamnatt Vijay Raghavan

Published in: COLT (1994)

Keyphrases

dnf formulas
membership queries
monotone dnf formulas
upper and lower bounds
concept class
uniform distribution
monotone dnf
boolean functions
term dnf
concept classes
special case
conjunctive queries
truth table
learning algorithm
statistical queries
query complexity
equivalence queries
data model