Exact learning of DNF formulas using DNF hypotheses

Lisa Hellerstein, Vijay Raghavan

    Research output: Contribution to journalArticle

    Abstract

    We show the following: (a) For any ε>0, log(3+ε)n-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries. (b) For sufficiently large t, t-term DNF formulas cannot be polynomial-query learned with membership and equivalence queries that use t1+ε-term DNF formulas as hypotheses, for some ε<1 (c) Read-thrice DNF formulas are not polynomial-query learnable with membership and proper equivalence queries. (d) logn-term DNF formulas can be polynomial-query learned with membership and proper equivalence queries. (This complements a result of Bshouty, Goldman, Hancock, and Matar that logn-term DNF can be so learned in polynomial time.) Versions of (a)-(c) were known previously, but the previous versions applied to polynomial-time learning and used complexity theoretic assumptions. In contrast, (a)-(c) apply to polynomial-query learning, imply the results for polynomial-time learning, and do not use any complexity-theoretic assumptions.

    Original languageEnglish (US)
    Pages (from-to)435-470
    Number of pages36
    JournalJournal of Computer and System Sciences
    Volume70
    Issue number4
    DOIs
    StatePublished - Jun 1 2005

    Keywords

    • Algorithms
    • Boolean functions
    • Certificates
    • Complexity theory
    • Computational learning theory
    • DNF
    • Disjunctive normal form

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Networks and Communications
    • Computational Theory and Mathematics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Exact learning of DNF formulas using DNF hypotheses'. Together they form a unique fingerprint.

  • Cite this