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

Krishnan Pillaipakkamnatt Vijay Raghavan

Published in: Mach. Learn. (1996)

Keyphrases

dnf formulas
membership queries
monotone dnf formulas
upper and lower bounds
uniform distribution
concept class
boolean functions
monotone dnf
randomly chosen
truth table
conjunctive queries
equivalence queries
efficient learning
learning theory
equivalence and membership queries