{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:17Z","timestamp":1787337497978,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for $k\\cdot j=O({\\log n\\over\\log\\log n})$, where n is the number of input variables.<\/jats:p>","DOI":"10.1137\/s0097539794274398","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1515-1530","source":"Crossref","is-referenced-by-count":8,"title":["On Learning Read-k-Satisfy-j DNF"],"prefix":"10.1137","volume":"27","author":[{"given":"Howard","family":"Aizenstein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avrim","family":"Blum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roni","family":"Khardon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonard","family":"Pitt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Roth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992675"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138061"},{"key":"R3","unstructured":"H. Aizenstein, L. Hellerstein, and L. Pitt,\n                      Read\u2010thrice DNF is hard to learn with membership and equivalence queries\n                      , In Proc. 33rd Symp. on the Foundations of Comp. Sci., IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 523\u2013532. A revised manuscript with additional results will appear in Comput. Complexity, as Aizenstein, Hegedus, Hellerstein, and Pitt,\n                      Complexity theoretic hardness results for query learning\n                      , to appear."},{"key":"R4","unstructured":"H. Aizenstein,\n                      On the Learnability of Disjunctive Normal Form Formulas and Decision Trees\n                      , Ph.D. thesis, Dept. of Computer Science, University of Illinois, Urbana, 1993;"},{"key":"R4","unstructured":"also Technical Report UIUCDCS\u2010R\u201093\u20101813, Dept. of Computer Science, University of Illinois, Urbana, 1993."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1026"},{"key":"R6","unstructured":"D. Angluin,\n                      Learning k\u2010Term DNF Formulas using Queries and Counterexamples\n                      , Technical Report YALEU\/DCS\/RR\u2010559, Department of Computer Science, Yale University, New Haven, CT, 1987."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116828"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116034"},{"key":"R9","unstructured":"H. Aizenstein and L. Pitt,\n                      Exact learning of read\u2010twice DNF formulas\n                      , In Proc. 32nd IEEE Symp. on Foundations of Computer Science, San Juan, 1991, pp. 170\u2013179."},{"key":"R10","unstructured":"H. Aizenstein and L. Pitt,\n                      Exact learning of read\u2010k disjoint DNF and not\u2010so\u2010disjoint DNF\n                      , in Proc. Annual ACM Workshop on Computational Learning Theory, Pittsburgh, PA, Morgan Kaufmann, San Francisco, 1992, pp. 71\u201376."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF00996269"},{"key":"R12","unstructured":"L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone,\n                      Classification and Regression Trees\n                      , Wadsworth International Group, CA, 1984."},{"key":"R13","first-page":"1515","volume":"27","author":"Aizenstein Howard","year":"1998","journal-title":"SIAM J. Comput."},{"key":"R14","unstructured":"A. Blum and S. Rudich,\n                      Fast learning of k\u2010term DNF formulas with queries\n                      , in Proc. 24th ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 382\u2013389."},{"key":"R15","unstructured":"A. Blum and M. Singh,\n                      Learning functions of k terms\n                      , In Proc. COLT \u201990, Morgan Kaufmann, San Francisco, 1990, pp. 144\u2013153."},{"key":"R16","unstructured":"N. H. Bshouty, personal communication, 1994."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1164"},{"key":"R18","unstructured":"G. Givaty, personal communication, 1995."},{"key":"R19","unstructured":"T. Hancock,\n                      Learning 2\u03bc DNF formulas and k\u03bc decision trees\n                      , In Proc. 4th Annual Workshop on Computational Learning Theory, Santa Cruz, CA, Morgan Kaufmann, San Francisco, 1991, pp. 199\u2013209."},{"key":"R20","unstructured":"J. Jackson,\n                      An efficient membership\u2010query algorithm for learning DNF with respect to the uniform distribution\n                      , in Proc. 35th IEEE Symp. on Foundations of Computer Science, Santa Fe, NM, 1994, pp. 42\u201353."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90057-4"},{"key":"R22","unstructured":"M. Kearns, M. Li, L. Pitt, and L. Valiant,\n                      On the learnability of Boolean formulae\n                      , In Proc. 19th Annual ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 285\u2013294."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"R24","first-page":"11","volume":"1","author":"Kushilevitz E.","year":"1995","journal-title":"Machine Learning","ISSN":"https:\/\/id.crossref.org\/issn\/0885-6125","issn-type":"print"},{"key":"R24","unstructured":"an earlier version appeared in Proc. ACM Workshop on Computational Learning Theory \u201993, ACM, New York."},{"key":"R25","unstructured":"S. Matar,\n                      Learning with Minimal Number of Queries\n                      , Master\u2019s thesis, University of Alberta, Canada, 1993."},{"key":"R26","unstructured":"K. Pillapakkamnatt and V. Raghavan,\n                      On the limits of proper learnability of subsets of DNF formulas\n                      , in Proc. Annual ACM Workshop on Computational Learning Theory, ACM, New York, 1994, pp. 118\u2013129;"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026455409889"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1149"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63140"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116251"},{"key":"R30","unstructured":"J. R. Quinlan,\n                      C4.5: Programs for machine learning\n                      , Morgan Kaufmann, San Francisco, 1993."},{"key":"R31","unstructured":"H. U. Simon,\n                      A tight \u03a9(loglogn)\u2010bound on the time for parallel RAM\u2019s to compute nondegenerate boolean functions\n                      , in Lecture Notes in Computer Science 158, Springer\u2010Verlag, New York, 1983, pp. 439\u2013444."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"R33","unstructured":"L. G. Valiant,\n                      Learning disjunctions of conjunctions\n                      , in Proc. 9th International Joint Conference on Artificial Intelligence, Vol. 1, Los Angeles, CA, 1985, pp. 560\u2013566."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794274398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:10Z","timestamp":1787336050000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794274398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794274398"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794274398","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}