TY - GEN

T1 - On learning read-k-satisfy-j DNF

AU - Blum, Avrim

AU - Khardont, Roni

AU - Kushilevitzi, Eyal

AU - Pitt, Leonard

AU - Rothf, Dan

N1 - Funding Information:
*e-mail: avrim@cs.cmu.edu. Research supported in part by an NSF Postdoctoral Fellowship and NSF National Youug Investigator grant CCR-93-57793. ‘e-mail: roni@das.harvard. edu. Research supported by grant DAAL03-92-G-0164 (Center for Intelligent Control Systems). $e-mail: eyaJk@cs.technion. ac.il. Part of this research was done while the author was at Aiken Computation Laboratory, Harvard University, supported by research contracts ONR-NOO01491-J-1981 and NSF-CCR-90-07677. $e-mail: pitt @cs.uiuc.edu. Research supported in part by NSF grant IRI-9014840. ‘e-mail: danr@daa.harvard .edu. Research supported NSF grant CCR-92-00884 and by DARPA AFOSR-F4962-92-J-0466.
Publisher Copyright:
© 1994 ACM.

PY - 1994/7/16

Y1 - 1994/7/16

N2 - We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k · j = O(log n/log log n)-Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size 2φ(√n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

AB - We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k · j = O(log n/log log n)-Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size 2φ(√n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

UR - http://www.scopus.com/inward/record.url?scp=84943226623&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84943226623&partnerID=8YFLogxK

U2 - 10.1145/180139.181051

DO - 10.1145/180139.181051

M3 - Conference contribution

AN - SCOPUS:84943226623

T3 - Proceedings of the Annual ACM Conference on Computational Learning Theory

SP - 110

EP - 117

BT - Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994

PB - Association for Computing Machinery

T2 - 7th Annual Conference on Computational Learning Theory, COLT 1994

Y2 - 12 July 1994 through 15 July 1994

ER -