On learning read-k-satisfy-j DNF

Avrim Blum, Roni Khardont, Eyal Kushilevitzi, Leonard Pitt, Dan Rothf

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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].

Original languageEnglish (US)
Title of host publicationProceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Electronic)0897916557
StatePublished - Jul 16 1994
Externally publishedYes
Event7th Annual Conference on Computational Learning Theory, COLT 1994 - New Brunswick, United States
Duration: Jul 12 1994Jul 15 1994

Publication series

NameProceedings of the Annual ACM Conference on Computational Learning Theory
VolumePart F129415


Other7th Annual Conference on Computational Learning Theory, COLT 1994
Country/TerritoryUnited States
CityNew Brunswick

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Artificial Intelligence


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

Cite this