Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-076 | 13th November 1998 00:00

Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution



We study attribute efficient learning in the PAC learning model with
membership queries. First, we give an {\it attribute efficient}
PAC-learning algorithm for DNF with membership queries under the
uniform distribution. Previous algorithms for DNF have sample size
polynomial in the number of attributes $n$. Our algorithm is the
first attribute efficient learning for DNF, i.e., that runs in polynomial
time and uses sample of size polynomial in $\log n$.
We also develop lower bound techniques for
PAC learning with membership queries under a fixed distribution
show that the sample size of our algorithm
for learning DNF under the uniform distribution
is almost optimal in terms of $n$.
Finally, we present a learning algorithm for DNF that is attribute
efficient in its use of random bits.

ISSN 1433-8092 | Imprint