TY - JOUR

T1 - Exact learning of DNF formulas using DNF hypotheses

AU - Hellerstein, Lisa

AU - Raghavan, Vijay

N1 - Funding Information:
Keywords: Computational learning theory; Disjunctive normal form; DNF; Boolean functions; Certificates; Algorithms; Complexity theory A preliminary version of this paper appeared in STOC 2002 [20]. ∗Corresponding author. E-mail addresses: hstein@brownstone.poly.edu (L. Hellerstein), raghavan@vuse.vanderbilt.edu (V. Raghavan). 1Research partially funded by NSF Grants CCR-9877122 and EIA-9806207. 2Research partially funded by NSF Grant CCR-9820840.

PY - 2005/6

Y1 - 2005/6

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

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

KW - Algorithms

KW - Boolean functions

KW - Certificates

KW - Complexity theory

KW - Computational learning theory

KW - DNF

KW - Disjunctive normal form

UR - http://www.scopus.com/inward/record.url?scp=17444399680&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=17444399680&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2004.10.001

DO - 10.1016/j.jcss.2004.10.001

M3 - Article

AN - SCOPUS:17444399680

SN - 0022-0000

VL - 70

SP - 435

EP - 470

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 4

ER -