Lisa Hellerstein (Polytechnic University, Brooklyn)
Certificates and the Learnability of DNF Formulas
We consider the problem of exact learning of DNF formulas using DNF
hypotheses. This problem is related to the complexity of DNF minimization.
Using certificate techniques, we prove upper and lower bounds on the query
complexity of learning t-term DNF formulas, for various values of t.