Read-thrice DNF is hard to learn with membership and equivalence queries

Howard Aizenstein, Lisa Hellerstein, Leonard Pitt

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

    Abstract

    A general technique is developed to obtain nonlearnability results in the model of exact learning from equivalence and membership queries. The technique is applied to show that, assuming NP not=co-NP, there does not exist a polynomial-time membership and equivalence query algorithm for exactly learning read-thrice DNF formulas-boolean formulas in disjunctive normal form where each variable appears at most three times. This result adds evidence to the conjecture that DNF is hard to learn in the membership and equivalence query model.

    Original languageEnglish (US)
    Title of host publicationProceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
    PublisherIEEE Computer Society
    Pages523-532
    Number of pages10
    ISBN (Electronic)0818629002
    DOIs
    StatePublished - 1992
    Event33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States
    Duration: Oct 24 1992Oct 27 1992

    Publication series

    NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
    Volume1992-October
    ISSN (Print)0272-5428

    Conference

    Conference33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
    CountryUnited States
    CityPittsburgh
    Period10/24/9210/27/92

    ASJC Scopus subject areas

    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Read-thrice DNF is hard to learn with membership and equivalence queries'. Together they form a unique fingerprint.

  • Cite this

    Aizenstein, H., Hellerstein, L., & Pitt, L. (1992). Read-thrice DNF is hard to learn with membership and equivalence queries. In Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 (pp. 523-532). [267799] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 1992-October). IEEE Computer Society. https://doi.org/10.1109/SFCS.1992.267799