On learning read-k satisfy-j DNF

Full Text

Authors:

A. Blum and R. Khardon and A. Kushilevitz and L. Pitt and Dan Roth

Abstract:

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. We show that this class of functions is learnable in polynomial time, using Equivalnce 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 fomulae but require CNF formulae off size 2Ω(sqrt(n)). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

Citation:

A. Blum and R. Khardon and A. Kushilevitz and L. Pitt and D. Roth, On learning read-k satisfy-j DNF. COLT  (1994) pp. 110--117

Bibitem:

@conference{BKKPR94,
  author = {A. Blum and R. Khardon and A. Kushilevitz and L. Pitt and D. Roth},
  title = {On learning read-k satisfy-j DNF},
  booktitle = {COLT},
  pages = {110--117},
  year = {1994},
  url = " http://cogcomp.cs.illinois.edu/papers/BKKPR94.pdf",
}