## 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 language | English (US) |
---|---|

Pages (from-to) | 435-470 |

Number of pages | 36 |

Journal | Journal of Computer and System Sciences |

Volume | 70 |

Issue number | 4 |

DOIs | |

State | Published - Jun 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