On learning read-k-satisfy-j DNF

Howard Aizenstein, Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth

Research output: Contribution to journalArticlepeer-review


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 · j = O(log n/log log n), where n is the number of input variables.

Original languageEnglish (US)
Pages (from-to)1515-1530
Number of pages16
JournalSIAM Journal on Computing
Issue number6
StatePublished - Dec 1998
Externally publishedYes


  • Computational learning theory
  • DNF
  • Decision trees
  • Learning

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'On learning read-k-satisfy-j DNF'. Together they form a unique fingerprint.

Cite this