An Efficient Membership-Query Algorithm
โ
Jeffrey C Jackson
๐
Article
๐
1997
๐
Elsevier Science
๐
English
โ 566 KB
We present a membership-query algorithm for efficiently learning DNF with respect to the uniform distribution. In fact, the algorithm properly learns with respect to uniform the class TOP of Boolean functions expressed as a majority vote over parity functions. We also describe extensions of this alg